An efficient algorithm for de novo peptide sequencing

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 in V such that v is a spectrum mass ion or that with complementary mass. 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, and is built in a progressive fashion using a priority queue, thus obtaining an improvement over other methods.