Construct the Graph of a Spectrum solved by 72

Sept. 18, 2015, 2:48 a.m. by Rosalind Team

We represent the masses in a spectrum as a sequence Spectrum of integers  $\textit{s}_\text{1}, \ldots, \textit{s}_\textit{m}$ in increasing order, where $\textit{s}_\text{1}$ is zero and $\textit{s}_\textit{m}$ is the total mass of the (unknown) peptide. We define a labeled graph Graph(Spectrum) by forming a node for each element of Spectrum, then connecting nodes $s_i$ and $s_j$ by a directed edge labeled by an amino acid $a$ if $s_j - s_i$ is equal to the mass of $a$. As we assumed when sequencing antibiotics, we do not distinguish between amino acids having the same integer masses (i.e., the pairs K/Q and I/L).

Spectrum Graph Construction

Construct the graph of a spectrum.

Given: A space-delimited list of integers Spectrum.

Return: Graph(Spectrum).

Note: In this chapter, all dataset problems implicitly use the standard integer-valued mass table for the regular twenty amino acids. Examples sometimes use imaginary amino acids X and Z having respective integer masses 4 and 5.

Sample Dataset

57 71 154 185 301 332 415 429 486

Sample Output

0->57:G
0->71:A
57->154:P
57->185:K
71->185:N
154->301:F
185->332:F
301->415:N
301->429:K
332->429:P
415->486:A
429->486:G

Extra Dataset

Please login to solve this problem.