title: Deconvolution and database search of complex tandem mass spectra of intact proteins: a combinatorial approach.
abstract: Top-down proteomics studies intact proteins, enabling new opportunities for analyzing post-translational modifications. Because tandem mass spectra of intact proteins are very complex, spectral deconvolution (grouping peaks into isotopomer envelopes) is a key initial stage for their interpretation. In such spectra, isotopomer envelopes of different protein fragments span overlapping regions on the m/z axis and even share spectral peaks. This raises both pattern recognition and combinatorial challenges for spectral deconvolution. We present MS-Deconv, a combinatorial algorithm for spectral deconvolution. The algorithm first generates a large set of candidate isotopomer envelopes for a spectrum, then represents the spectrum as a graph, and finally selects its highest scoring subset of envelopes as a heaviest path in the graph. In contrast with other approaches, the algorithm scores sets of envelopes rather than individual envelopes. We demonstrate that MS-Deconv improves on Thrash and Xtract in the number of correctly recovered monoisotopic masses and speed. We applied MS-Deconv to a large set of top-down spectra from Yersinia rohdei (with a still unsequenced genome) and further matched them against the protein database of related and sequenced bacterium Yersinia enterocolitica. MS-Deconv is available at http://proteomics.ucsd.edu/Software.html.
authors.affiliation: Department of Computer Science and Engineering, University of California, San Diego, California 92093, USA.
authors.forename: Xiaowen
authors.initials: X
authors.lastname: Liu
authors.forename: Yuval
authors.initials: Y
authors.lastname: Inbar
authors.forename: Pieter C
authors.initials: PC
authors.lastname: Dorrestein
authors.forename: Colin
authors.initials: C
authors.lastname: Wynne
authors.forename: Nathan
authors.initials: N
authors.lastname: Edwards
authors.forename: Puneet
authors.initials: P
authors.lastname: Souda
authors.forename: Julian P
authors.initials: JP
authors.lastname: Whitelegge
authors.forename: Vineet
authors.initials: V
authors.lastname: Bafna
authors.forename: Pavel A
authors.initials: PA
authors.lastname: Pevzner
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D020650:Combinatorial Chemistry Techniques; D030562:Databases, Protein; D008969:Molecular Sequence Data; D011506:Proteins / Q000737:chemistry*; D053719:Tandem Mass Spectrometry / Q000379:methods*
chemical_list: D011506:Proteins