Perfect Matchings and RNA Secondary Structures(완벽 매칭)

https://rosalind.info/problems/pmch/

ROSALIND | Perfect Matchings and RNA Secondary Structures

Problem

Figure 2. Three matchings (highlighted in red) shown in three different graphs.

Figure 3. A graph containing 10 nodes; the five edges forming a perfect matching on these nodes are highlighted in red.

Figure 4. The bonding graph for the RNA string s = UAGCGUGAUCAC.

Figure 5. A perfect matching on the basepair edges is highlighted in red and represents a candidate secondary structure for the RNA strand.

A matching in a graph GG is a collection of edges of GG for which no node belongs to more than one edge in the collection. See Figure 2 for examples of matchings. If GG contains an even number of nodes (say 2n2n), then a matching on GG is perfect if it contains nn edges, which is clearly the maximum possible. An example of a graph containing a perfect matching is shown in Figure 3.

First, let KnKn denote the complete graph on 2n2n labeled nodes, in which every node is connected to every other node with an edge, and let pnpn denote the total number of perfect matchings in KnKn. For a given node xx, there are 2n−12n−1 ways to join xx to the other nodes in the graph, after which point we must form a perfect matching on the remaining 2n−22n−2 nodes. This reasoning provides us with the recurrence relation pn=(2n−1)⋅pn−1pn=(2n−1)⋅pn−1; using the fact that p1p1 is 1, this recurrence relation implies the closed equation pn=(2n−1)(2n−3)(2n−5)⋯(3)(1)pn=(2n−1)(2n−3)(2n−5)⋯(3)(1).

Given an RNA string s=s1…sns=s1…sn, a bonding graph for ss is formed as follows. First, assign each symbol of ss to a node, and arrange these nodes in order around a circle, connecting them with edges called adjacency edges. Second, form all possible edges {A, U} and {C, G}, called basepair edges; we will represent basepair edges with dashed edges, as illustrated by the bonding graph in Figure 4.

Note that a matching contained in the basepair edges will represent one possibility for base pairing interactions in ss, as shown in Figure 5. For such a matching to exist, ss must have the same number of occurrences of 'A' as 'U' and the same number of occurrences of 'C' as 'G'.

Given: An RNA string ss of length at most 80 bp having the same number of occurrences of 'A' as 'U' and the same number of occurrences of 'C' as 'G'.

Return: The total possible number of perfect matchings of basepair edges in the bonding graph of ss.

Sample Dataset

>Rosalind_23
AGCUAGUCAU

Sample Output

12

 

 이 문제는 FASTA 파일로 RNA가 주어졌을 때 perfect matching의 가짓수를 구하는 문제이다. 이 문제에서의 perfect matching이란 같은 서열에서 모든 A는 U와, 모든 C는 G와 짝이 지어지고 짝이 없는 염기는 없을 때를 말한다. 

 이 문제는 그저 A와 C의 개수를 구해서 U,G와 짝 지어지는 경우의 수를 구하면 된다. 이는 A와 C의 순열을 구하면 된다. 순열은 팩토리얼로 구할 수 있으므로 A와 C의 개수의 팩토리얼을 곱하면 된다

from Bio import SeqIO

def fact(n):
    re=1
    for i in range(1,n+1):
        re*=i
    return re
if __name__=='__main__':
    with open(r'파일경로','r') as fa:
        for s in SeqIO.parse(fa,'fasta'):
            seq=s.seq

A,C=0,0
for i in seq:
    if i == 'A':
        A+=1
    elif i == 'C':
        C+=1

print(fact(A)*fact(C))