A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry.
Tandem mass spectrometry has emerged to be one of the most powerful high-throughput techniques for protein identification. Tandem mass spectrometry selects and fragments peptides of interest into N-terminal ions and C-terminal ions, and it measures the mass/charge ratios of these ions. The de novo peptide sequencing problem is to derive the peptide sequences from given tandem mass spectral data of k ion peaks without searching against protein databases. By transforming the spectral data into a matrix spectrum graph G = (V, E), where |V| = O(k(2)) and |E| = O(k(3)), we give the first polynomial time suboptimal algorithm that finds all the suboptimal solutions (peptides) in O(p|E|) time, where p is the number of solutions. The algorithm has been implemented and tested on experimental data. The program is available at http://hto-c.usc.edu:8000/msms/menu/denovo.htm.
Lu
Bingwen
B
Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089, USA.
Chen
Ting
T
D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D001798:Blood Proteins; D002417:Cattle; D013058:Mass Spectrometry / Q000379:methods*; D008969:Molecular Sequence Data; D010455:Peptides / Q000737:chemistry*; D011506:Proteins / Q000737:chemistry; D011786:Quality Control; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D020539:Sequence Analysis, Protein / Q000379:methods*; D012710:Serum Albumin, Bovine / Q000737:chemistry
D001798:Blood Proteins; D010455:Peptides; D011506:Proteins; D012710:Serum Albumin, Bovine