Using the Spectrum Graph to Infer Peptides

https://rosalind.info/problems/sgra/

ROSALIND | Using the Spectrum Graph to Infer Peptides

Problem

For a weighted alphabet AA and a collection LL of positive real numbers, the spectrum graph of LL is a digraph constructed in the following way. First, create a node for every real number in LL. Then, connect a pair of nodes with a directed edge (u,v)(u,v) if v>uv>u and v−uv−u is equal to the weight of a single symbol in AA. We may then label the edge with this symbol.

In this problem, we say that a weighted string s=s1s2⋯sns=s1s2⋯sn matches LL if there is some increasing sequence of positive real numbers (w1,w2,…,wn+1)(w1,w2,…,wn+1) in LL such that w(s1)=w2−w1w(s1)=w2−w1, w(s2)=w3−w2w(s2)=w3−w2, ..., and w(sn)=wn+1−wnw(sn)=wn+1−wn.

Given: A list LL (of length at most 100) containing positive real numbers.

Return: The longest protein string that matches the spectrum graph of LL (if multiple solutions exist, you may output any one of them). Consult the monoisotopic mass table.

Sample Dataset

3524.8542
3623.5245
3710.9335
3841.974
3929.00603
3970.0326
4026.05879
4057.0646
4083.08025

Sample Output

WMSPG

 

 이 문제는 주어진 스펙트럼들을 이용하여 추론해낼 수 있는 최대길이의 펩타이드 서열을 출력하는 문제이다. 이 문제를 풀기 위해서는 일단 스펙트럼 그래프를 만들어야한다. 이 그래프는 스펙트럼들이 노드이며 정확히 아미노산 하나의 차이가 나는 스펙트럼 끼리 엣지로 이어진다. 이때 엣지는 나는 작은 노드에서 큰 노드로 향하는 directed edge로 하였고, 그 아미노산이 edge를 라벨한다.

 이런 식으로 만든 그래프를 이용해 DFS를 활용해 만들어 질 수 있는 긴 펩타이들을 모아 정렬을 하여 가장 긴 펩타이드를 출력하였다.

 이 문제는 정수형을 다루는 지라 round()함수를 이용해 반올림으로 풀어갈려 했지만 에러가 사실은 +- 로 일어나서 별로 좋지 않아 에러를 감안해주는 함수를 따로 만들어 아예 아미노산까지 리턴하도록 만들었다.

from collections import defaultdict

spec_to_AA_table={
    71.03711: 'A', 103.00919: 'C', 115.02694: 'D', 129.04259: 'E', 147.06841: 'F', 
    57.02146: 'G', 137.05891: 'H', 113.08406: 'L', 128.09496: 'K', 131.04049: 'M', 
    114.04293: 'N', 97.05276: 'P', 128.05858: 'Q', 156.10111: 'R', 87.03203: 'S', 
    101.04768: 'T', 99.06841: 'V', 186.07931: 'W', 163.06333: 'Y'
    }
def in_error(real_weight,error):#에러 감안하여 AA리턴
    for item in spec_to_AA_table.items():
        if abs(item[0]-real_weight) < error:
            return item[1]
    return None

def making_graph(specs):#그래프 만들기
    spec_graph = defaultdict(list)

    for i in range(len(specs)-1):
        for j in range(i+1,len(specs)):
            if specs[j] - specs[i] > max(spec_to_AA_table.keys())+1:
                break
            temp_pro = in_error(specs[j]-specs[i],0.001)
            if temp_pro is not None:
                spec_graph[i].append([temp_pro,j])
    
    return spec_graph

def making_peptides(now_node,peptide,graph):#DFS로 탐색
    if graph[now_node] == []:
        total_pep.append(peptide)
        return 
    for pep,new_node in graph[now_node]:
        making_peptides(new_node,peptide+pep,graph)

total_pep=[]#만들어지는 펩타이드들 저장


if __name__ == '__main__':
    with open(r"파일경로",'r') as rf:
        specs=sorted([float(i.rstrip()) for i in rf.readlines()])
AA_spec = spec_to_AA_table.keys()
graph=making_graph(specs)
for i in range(len(specs)):
    making_peptides(i,'',graph)

print(sorted(total_pep,key=len,reverse=True)[0])#가장 긴거 출력