Mining Mass Spectra: Metric Embeddings and Fast Near Neighbor Search

Mining large-scale high-throughput tandem mass spectrometry data sets is a very important problem in mass spectrometry based protein identification. One of the fundamental problems in large scale mining of spectra is to design appropriate metrics and algorithms to avoid all-pair-wise comparisons of spectra. In this paper, we present a general framework based on vector spaces to avoid pair-wise comparisons. We first robustly embed spectra in a high dimensional space in a novel fashion and then apply fast approximate near neighbor algorithms for tasks such as constructing filters for database search, indexing and similarity searching. We formally prove that our embedding has low distortion compared to the cosine similarity, and, along with locality sensitive hashing (LSH), we design filters for database search that can filter out more than 989% of peptides (118 times less) while missing at most 0.29% of the correct sequences. We then show how our framework can be used in similarity searching, which can then be used to detect tight clusters or replicates. On an average, for a cluster size of 16 spectra, LSH only misses 1 spectrum and admits only 1 false spectrum. In addition, our framework in conjunction with dimension reduction techniques allow us to visualize large datasets in 2D space. Our framework also has the potential to embed and compare datasets with post translation modifications (PTM).