Maximum Matchings and RNA Secondary Structures

https://rosalind.info/problems/mmch/

ROSALIND | Maximum Matchings and RNA Secondary Structures

Problem

Figure 1. The bonding graph of s = UAGCGUGAUCAC (left) has a perfect matching of basepair edges, but this is not the case for t = CAGCGUGAUCAC (right), in which one symbol has been replaced.

Figure 2. A maximum matching (highlighted in red) is shown in each of the three graphs above. You can verify that no other matching can contain more edges. (Courtesy: Miym, Wikimedia Commons User)

Figure 3. A red maximum matching of basepair edges in the bonding graph for t = CAGCGUGAUCAC.

The graph theoretical analogue of the quandary stated in the introduction above is that if we have an RNA string ss that does not have the same number of occurrences of 'C' as 'G' and the same number of occurrences of 'A' as 'U', then the bonding graph of ss cannot possibly possess a perfect matching among its basepair edges. For example, see Figure 1; in fact, most bonding graphs will not contain a perfect matching.

In light of this fact, we define a maximum matching in a graph as a matching containing as many edges as possible. See Figure 2 for three maximum matchings in graphs.

A maximum matching of basepair edges will correspond to a way of forming as many base pairs as possible in an RNA string, as shown in Figure 3.

Given: An RNA string ss of length at most 100.

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

Sample Dataset

>Rosalind_92
AUGCUUC

Sample Output

6

 

 이 문제는 maximum matching의 경우의 수를 구하는 문제이다. maximum matching은 가능한 최대한 많이 짝을 지었을 때의 매칭을 말한다. 이는 즉 A가 4개 U가 3개라면 짝은 3개가 지어진단 소리다. 이 경우의 수는 구분되는 n개를 구분되는 r개에 짝을 짓는 경우의 수이다. 이는 n!/(n-r)!로 정의가 된다. 이를 코드로 구현하면 끝이다.

from Bio import SeqIO

def factorial(n):
    ret=1
    for i in range(1,n+1):
        ret*=i
    
    return ret

def combination(n,r):

    return factorial(n)//(factorial(n-r))

if __name__=='__main__':
    with open(r'파일경로','r') as fa:
        S=str(next(SeqIO.parse(fa,'fasta')).seq)

A,C,G,U = S.count('A'),S.count('C'),S.count('G'),S.count('U')

AU,CG = sorted([A,U]),sorted([C,G])

print(combination(AU[1],AU[0])*combination(CG[1],CG[0]))