PRIME: A Mass Spectrum Data Mining Tool for <Emphasis Type="Italic">De Nova</Emphasis> Sequencing and PTMs Identification

sequencing is one of the most promising proteomics techniques for identification of protein post-translation modifications (PTMs) in studying protein regulations and functions. We have developed a computer tool PRIME for identification of b and y ions in tandem mass spectra, a key challenging problem in de novo sequencing. PRIME utilizes a feature that ions of the same and different types follow different mass-difference distributions to separate b from y ions correctly. We have formulated the problem as a graph partition problem. A linear integer-programming algorithm has been implemented to solve the graph partition problem rigorously and efficiently. The performance of PRIME has been demonstrated on a large amount of simulated tandem mass spectra derived from Yeast genome and its power of detecting PTMs has been tested on 216 simulated phosphopeptides. This research was supported in part by the National Science Foundation of U.S.A (Grant Nos.NSF/DBI-0354771 and #NSF/ITR-IIS-0407204). It was also funded in part by the U.S. Department of Energy's Genomes to Life program (http://doegenomestolife.org/) under project, “Carbon Sequestration in Synechococcus sp.: From Molecular Machines to Hierarchical Modeling” (www.genomes2life.org). Bo Yan received his Ph.D. degree in chemistry from Peking University. He is now working in the Computational Systems Biology Lab at University of Georgia, USA. His research interests include Monte Carlo simulations, graph theory, computational biology/chemistry and bioinformatics. You-Xing Qu received his Ph.D. degree in biophysics from Peking University, China. Currently he is working in the Computational Systems Biology Lab at the University of Georgia, USA. His research interests include computational biology, protein folding, structural biology, and biophysics. Feng-Lou Mao received his Ph.D. degree in computational chemistry from Peking University in 2001. He is now a postdoc researcher at University of Georgia, USA. His current research interests include bioinformatics, systems biology and computational biology. Victor N. Olman is a Senior Research Scientist in Biochemistry and Molecular Biology Department of UGA. He got the Ph.D. degree in mathematics from S. Petersburg University, Russia. Right now his main interests are in the field of mathematical applications in bioinformatics that include methods of mathematical statistics, graph theory, simulation and modeling of dynamic systems. He is a member of American Statistical Association. Ying Xu is a chair professor of bioinformatics and computational biology in the Biochemistry and Molecular Biology Department, and the director of the Institute of Bioinformatics, University of Georgia, USA. Before joining UGA in Sept 2003, he was a senior staff scientist and group leader at Oak Ridge National Laboratory, USA, where he still holds a joint position. He also holds guest or research professor positions at the University of Tennessee at Knoxville of USA, Jilin University and Zhejiang University of China, and an adjunct professor position in the Computer Science Department of UGA. Ying Xu received his undergraduate and graduate education in computer science from Jilin University, and Ph.D. degree in theoretical computer science from the University of Colorado at Boulder of USA in 1991. He is interested in both bioinformatics tool development and study of biological problems using in silico approaches. His current research interests include (a) computational inference and modeling of biological pathways and networks, (b) protein structure prediction and modeling, (c) large-scale biological data mining, and (d) microbial & cancer bioinformatics.