1. An Efficient Algorithm for De Novo Peptide Sequencing.
- Author
-
Ribeiro, Bernardete, Albrecht, Rudolf F., Dobnikar, Andrej, Pearson, David W., Steele, Nigel C., Brunetti, S., Dutta, D., Liberatori, S., Mori, E., and Varrazzo, D.
- Subjects
AMINO acid sequence ,ALGORITHMS ,SPECTRUM analysis ,DYNAMIC programming ,SYSTEMS engineering - Abstract
In this paper we propose a new algorithm for the de novo peptide sequencing problem. This problem reconstructs a peptide sequence from a given tandem mass spectra data containing n peaks. We first build a directed acyclic graph G = (V, E) in O(n log n) time, where v ∊ V is a spectrum mass ion or a complementary mass to a spectrum ion. The solutions of this problem are then given by the paths in the graph between two designated vertices. Unlike previous approaches, the proposed algorithm does not use dynamic programming, but it builds the graph in a progressive fashion using a priority queue, thus obtaining an improvement over other methods [1,2]. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF