Matching a Spectrum to a Protein

https://rosalind.info/problems/prsm/

ROSALIND | Matching a Spectrum to a Protein

Problem

The complete spectrum of a weighted string ss is the multiset S[s]S[s] containing the weights of every prefix and suffix of ss.

Given: A positive integer nn followed by a collection of nn protein strings s1s1, s2s2, ..., snsn and a multiset RR of positive numbers (corresponding to the complete spectrum of some unknown protein string).

Return: The maximum multiplicity of R⊖S[sk]R⊖S[sk] taken over all strings sksk, followed by the string sksk for which this maximum multiplicity occurs (you may output any such value if multiple solutions exist).

Sample Dataset

4
GSDMQS
VWICN
IASWMQS
PVSMGAD
445.17838
115.02694
186.07931
314.13789
317.1198
215.09061

Sample Output

3
IASWMQS

 

 이 문제는 정수형 n과 n개의 단백질 서열들, 그리고 미지의 단백질의 complete spectrum R이 주어진다. 이때 우리가 구해야할 것은 R과 각 단백질 서열의 complet spectrum의 민코프스키 차를 구하고 이때 최대 multiplicity를 구하고 이 최대가 어느 서열에서 나왔는지 출력하는 문제이다.

 complet spectrum은 단백질 서열에서 모든 prefix,suffix의 스펙트럼의 집합이다. 민코프스키 차는 두 집합 안의 원소를 각각 다 뺀 값의 다중집합이다. multitplicity는 다중 집합에서 어떠한 요소가 몇 번 나왔는가이다. 이러한 개념을 갖고, 차분하게 구현해나가면 문제는 풀린다.

monoisotopic_mass_table={
    'A':71.03711, 'C':103.00919, 'D':115.02694, 'E':129.04259,
    'F':147.06841, 'G':57.02146, 'H':137.05891, 'I':113.08406, 'K':128.09496,
    'L':113.08406,
    'M':131.04049, 'N':114.04293, 'P':97.05276, 'Q':128.05858,
    'R':156.10111, 'S':87.03203, 'T':101.04768, 'V':99.06841, 
    'W':186.07931, 'Y':163.06333 
}

def making_S(prt):#complete spectrum
    S=set()
    pre=0
    for p in prt:
        pre+=monoisotopic_mass_table[p]
        S.add(round(pre,5))
    
    suf=0
    for s in prt[::-1]:
        suf+=monoisotopic_mass_table[s]
        S.add(round(suf,5))
    
    return list(S)

def making_Min(S,R):#민코프스키차
    convolution = [round(r-s,5) for s in S for r in R]
    convolution_count = {s:convolution.count(s) for s in convolution}
    max_ = max(convolution_count.values())
    return max_

with open(r"파일경로",'r') as f:
    n = int(f.readline().rstrip())
    prts=[]
    for _ in range(n):
        prts.append(f.readline().rstrip())
    
    R=[]
    for i in f.readlines():
        R.append(float(i.rstrip()))
    
    total_max=-1
    total_max_protein=''
    for prt in prts:#단백질 돌며 구하기
        S=making_S(prt)
        now_max=making_Min(S,R)
        if now_max >= total_max:
            total_max=now_max
            total_max_protein=prt
    
    print(total_max)
    print(total_max_protein)