A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry
<|reference_start|>A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry: The tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged prefix and suffix subsequences, and then measures mass/charge ratios of these ions. The de novo peptide sequencing problem is to reconstruct the peptide sequence from a given tandem mass spectral data of k ions. By implicitly transforming the spectral data into an NC-spectrum graph G=(V,E) where |V|=2k+2, we can solve this problem in O(|V|+|E|) time and O(|V|) space using dynamic programming. Our approach can be further used to discover a modified amino acid in O(|V||E|) time and to analyze data with other types of noise in O(|V||E|) time. Our algorithms have been implemented and tested on actual experimental data.<|reference_end|>
@article{chen2001a,
    title={A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem
  Mass Spectrometry},
    author={Ting Chen, Ming-Yang Kao, Matthew Tepel, John Rush, George M. Church},
    journal={arXiv preprint arXiv:cs/0101016},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0101016},
    primaryClass={cs.CE cs.DS}
}