sgra.py

import numpy as np
from collections import defaultdict

protein_mass={}
mass_to_protein={}
with open("protein_masses.txt","rU") as f:
    for line in f:
        x=line.split()
        protein_mass[x[0]]=round(float(x[1]),4)
        mass_to_protein[round(float(x[1]),4)]=x[0]        
def mass(x):
    m=0
    for s in x:
        m+=protein_mass[s]
    return m

masses=[]
with open("rosalind_sgra.txt","rU") as f:
    for line in f:
        masses.append(round(float(line),6))
n=len(masses)
successors=defaultdict(list)
predecessors=defaultdict(list)

for i in range(n):
    for j in range(n):
        if masses[j]>masses[i] and round(masses[j]-masses[i],4) in mass_to_protein:
            successors[i].append(j)
            predecessors[j].append(i)

dp=np.zeros(len(masses),dtype=int)
pred=np.zeros(len(masses),dtype=int)

for i in range(len(masses)):
    for j in successors[i]:
        if dp[j]<=dp[i]+1:
            dp[j]=dp[i]+1
            pred[j]=i
            
i=np.argmax(dp)
s=''
while pred[i]!=0:
    s=mass_to_protein[round(masses[i]-masses[pred[i]],4)]+s
    i=pred[i]
s=mass_to_protein[round(masses[i]-masses[pred[i]],4)]+s
print s