Bioinformatics Advance Access published online on January 19, 2007
Bioinformatics, doi:10.1093/bioinformatics/btl645
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Speeding up Tandem Mass Spectrometry Database Search: Metric Embeddings and Fast Near Neighbor Search
a1050 Childs Way, bLos Angeles, CA 90089, USA
*The authors are with the Department of Computational Biology, University of Southern California, Los Angeles 90089. They can be contacted at ddutta{at}usc.edu, tingchen{at}usc.edu respectively
 |
Abstract |
|---|
Motivation: Due to the recent advances in technology of mass spectrometry, there has been an exponential increase in the amount of data being generated in the past few years. Database searches have not been able to keep up with this data explosion. Thus, speeding up the data searches becomes increasingly important in mass spectrometry based applications. Traditional database search methods use one-against-all comparisons of a query spectrum against a very large number of peptides generated from in-silico digestion of protein sequences in a database, to filter potential candidates from this database followed by a detailed scoring and ranking of those filtered candidates.
Results: In this paper, we show that we can avoid the one-against-all comparisons. The basic idea s to design a set of hash functions to pre-process peptides in the database such that for each query spectrum we can use the hash functions to find only a small subset of peptide sequences that are most likely to match the spectrum. The construction of each hash function is based on a random spectrum and the hash value of a peptide is the normalized shared peak counts score (cosine) between the random spectrum and the hypothetical spectrum of the peptide. To implement this idea, we first embed each peptide into a unit vector in a high dimensional metric space. The random spectrum is represented by a random vector, and we use random vectors to construct a set of hash functions called locality sensitive hashing (LSH) for preprocessing. We demonstrate that our mapping is accurate. We show that our method can filter out more than 95.65% of the spectra without missing any correct sequences, or gain 111 times speedup by filtering out 99.64% of spectra while missing at most 0.19% (2 out of 1014) of the correct sequences. In addition, we show that our method can be effectively used for other mass spectra mining applications such as finding clusters of spectra efficiently and accurately.
Associate Editor: Alfonso Valencia
Received on March 28, 2006; revised on December 16, 2006; accepted on December 18, 2006
CiteULike 
Connotea 
Del.icio.us What's this?