Faster and more accurate graphical model identification of tandem mass spectra using trellises.
Tandem mass spectrometry (MS/MS) is the dominant high throughput technology for identifying and quantifying proteins in complex biological samples. Analysis of the tens of thousands of fragmentation spectra produced by an MS/MS experiment begins by assigning to each observed spectrum the peptide that is hypothesized to be responsible for generating the spectrum. This assignment is typically done by searching each spectrum against a database of peptides. To our knowledge, all existing MS/MS search engines compute scores individually between a given observed spectrum and each possible candidate peptide from the database. In this work, we use a trellis, a data structure capable of jointly representing a large set of candidate peptides, to avoid redundantly recomputing common sub-computations among different candidates. We show how trellises may be used to significantly speed up existing scoring algorithms, and we theoretically quantify the expected speedup afforded by trellises. Furthermore, we demonstrate that compact trellis representations of whole sets of peptides enables efficient discriminative learning of a dynamic Bayesian network for spectrum identification, leading to greatly improved spectrum identification accuracy.



bilmes@uw.edu or william-noble@uw.edu



Supplementary data are available at Bioinformatics online.
Department of Computer Science and Engineering.
Shengjie
S
Wang
Department of Electrical Engineering.
John T
JT
Halloran
Department of Computer Science and Engineering Department of Electrical Engineering.
Jeff A
JA
Bilmes
Department of Computer Science and Engineering Department of Genome Sciences, University of Washington, Seattle, WA 98195, USA.
William S
WS
Noble
D000465:Algorithms; D001499:Bayes Theorem; D030562:Databases, Protein; D010455:Peptides; D011506:Proteins; D040901:Proteomics; D053719:Tandem Mass Spectrometry
D010455:Peptides; D011506:Proteins