title: A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry.
abstract: 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.
authors.affiliation: Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089, USA.
authors.forename: Bingwen
authors.initials: B
authors.lastname: Lu
authors.forename: Ting
authors.initials: T
authors.lastname: Chen
mesh_terms: 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
chemical_list: D001798:Blood Proteins; D010455:Peptides; D011506:Proteins; D012710:Serum Albumin, Bovine