1
|
Bittremieux W, Laukens K, Noble WS, Dorrestein PC. Large-scale tandem mass spectrum clustering using fast nearest neighbor searching. RAPID COMMUNICATIONS IN MASS SPECTROMETRY : RCM 2021:e9153. [PMID: 34169593 PMCID: PMC8709870 DOI: 10.1002/rcm.9153] [Citation(s) in RCA: 7] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/05/2021] [Revised: 06/21/2021] [Accepted: 06/21/2021] [Indexed: 05/27/2023]
Abstract
RATIONALE Advanced algorithmic solutions are necessary to process the ever-increasing amounts of mass spectrometry data that are being generated. In this study, we describe the falcon spectrum clustering tool for efficient clustering of millions of MS/MS spectra. METHODS falcon succeeds in efficiently clustering large amounts of mass spectral data using advanced techniques for fast spectrum similarity searching. First, high-resolution spectra are binned and converted to low-dimensional vectors using feature hashing. Next, the spectrum vectors are used to construct nearest neighbor indexes for fast similarity searching. The nearest neighbor indexes are used to efficiently compute a sparse pairwise distance matrix without having to exhaustively perform all pairwise spectrum comparisons within the relevant precursor mass tolerance. Finally, density-based clustering is performed to group similar spectra into clusters. RESULTS Several state-of-the-art spectrum clustering tools were evaluated using a large draft human proteome data set consisting of 25 million spectra, indicating that alternative tools produce clustering results with different characteristics. Notably, falcon generates larger highly pure clusters than alternative tools, leading to a larger reduction in data volume without the loss of relevant information for more efficient downstream processing. CONCLUSIONS falcon is a highly efficient spectrum clustering tool, which is publicly available as an open source under the permissive BSD license at https://github.com/bittremieux/falcon.
Collapse
Affiliation(s)
- Wout Bittremieux
- Skaggs School of Pharmacy and Pharmaceutical Sciences, University of California San Diego, La Jolla, California, United States
- Department of Computer Science, University of Antwerp, Antwerp, Belgium
| | - Kris Laukens
- Department of Computer Science, University of Antwerp, Antwerp, Belgium
| | - William Stafford Noble
- Department of Genome Sciences, University of Washington, Seattle, Washington, United States
| | - Pieter C Dorrestein
- Skaggs School of Pharmacy and Pharmaceutical Sciences, University of California San Diego, La Jolla, California, United States
| |
Collapse
|
2
|
Silva ARF, Lima DB, Kurt LU, Dupré M, Chamot-Rooke J, Santos MDM, Nicolau CA, Valente RH, Barbosa VC, Carvalho PC. Leveraging the partition selection bias to achieve a high-quality clustering of mass spectra. J Proteomics 2021; 245:104282. [PMID: 34089898 DOI: 10.1016/j.jprot.2021.104282] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/12/2021] [Revised: 05/25/2021] [Accepted: 05/30/2021] [Indexed: 11/25/2022]
Abstract
In proteomics, the identification of peptides from mass spectral data can be mathematically described as the partitioning of mass spectra into clusters (i.e., groups of spectra derived from the same peptide). The way partitions are validated is just as important, having evolved side by side with the clustering algorithms themselves and given rise to many partition assessment measures. An assessment measure is said to have a selection bias if, and only if, the probability that a randomly chosen partition scoring a high value depends on the number of clusters in the partition. In the context of clustering mass spectra, this might mislead the validation process to favor clustering algorithms that generate too many (or few) spectral clusters, regardless of the underlying peptide sequence. A selection bias toward the number of peptides is desirable for proteomics as it estimates the number of peptides in a complex protein mixture. Here, we introduce an assessment measure that is purposely biased toward the number of peptide ion species. We also introduce a partition assessment framework for proteomics, called the Partition Assessment Tool, and demonstrate its importance by evaluating the performance of eight clustering algorithms on seven proteomics datasets while discussing the trade-offs involved. SIGNIFICANCE: Clustering algorithms are widely adopted in proteomics for undertaking several tasks such as speeding up search engines, generating consensus mass spectra, and to aid in the classification of proteomic profiles. Choosing which algorithm is most fit for the task at hand is not simple as each algorithm has advantages and disadvantages; furthermore, specifying clustering parameters is also a necessary and fundamental step. For example, deciding on whether to generate "pure clusters" or fewer clusters but accepting noise. With this as motivation, we verify the performance of several widely adopted algorithms on proteomic datasets and introduce a theoretical framework for drawing conclusions on which approach is suitable for the task at hand.
Collapse
Affiliation(s)
- André R F Silva
- Laboratory of Structural and Computational Proteomics, Carlos Chagas Institute, Fiocruz Paraná, Brazil.
| | - Diogo B Lima
- Department of Chemical Biology, Leibniz - Forschungsinstitut für Molekulare Pharmakologie (FMP), Berlin, Germany
| | - Louise U Kurt
- Laboratory of Structural and Computational Proteomics, Carlos Chagas Institute, Fiocruz Paraná, Brazil
| | - Mathieu Dupré
- Mass Spectrometry for Biology Unit, CNRS USR 2000, Institut Pasteur, Paris, France
| | - Julia Chamot-Rooke
- Mass Spectrometry for Biology Unit, CNRS USR 2000, Institut Pasteur, Paris, France
| | - Marlon D M Santos
- Laboratory of Structural and Computational Proteomics, Carlos Chagas Institute, Fiocruz Paraná, Brazil
| | - Carolina Alves Nicolau
- Laboratory of Toxinology, Oswaldo Cruz Institute, Fiocruz, Rio de Janeiro, Rio de Janeiro, Brazil; Centre de Recherche en Cancérologie et Immunologie Nantes-Angers (CRCINA), Team SOAP, INSERM U1232, Nantes, France
| | - Richard Hemmi Valente
- Laboratory of Toxinology, Oswaldo Cruz Institute, Fiocruz, Rio de Janeiro, Rio de Janeiro, Brazil
| | - Valmir C Barbosa
- Systems Engineering and Computer Science Program, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil.
| | - Paulo C Carvalho
- Laboratory of Structural and Computational Proteomics, Carlos Chagas Institute, Fiocruz Paraná, Brazil.
| |
Collapse
|
3
|
Rawlinson C, Jones D, Rakshit S, Meka S, Moffat CS, Moolhuijzen P. Hierarchical clustering of MS/MS spectra from the firefly metabolome identifies new lucibufagin compounds. Sci Rep 2020; 10:6043. [PMID: 32269256 PMCID: PMC7142086 DOI: 10.1038/s41598-020-63036-1] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/09/2019] [Accepted: 03/24/2020] [Indexed: 01/09/2023] Open
Abstract
Metabolite identification is the greatest challenge when analysing metabolomics data, as only a small proportion of metabolite reference standards exist. Clustering MS/MS spectra is a common method to identify similar compounds, however interrogation of underlying signature fragmentation patterns within clusters can be problematic. Previously published high-resolution LC-MS/MS data from the bioluminescent beetle (Photinus pyralis) provided an opportunity to mine new specialized metabolites in the lucibufagin class, compounds important for defense against predation. We aimed to 1) provide a workflow for hierarchically clustering MS/MS spectra for metabolomics data enabling users to cluster, visualise and easily interrogate the identification of underlying cluster ion profiles, and 2) use the workflow to identify key fragmentation patterns for lucibufagins in the hemolymph of P. pyralis. Features were aligned to their respective MS/MS spectra, then product ions were dynamically binned and resulting spectra were hierarchically clustered and grouped based on a cutoff distance threshold. Using the simplified visualization and the interrogation of cluster ion tables the number of lucibufagins was expanded from 17 to a total of 29.
Collapse
Affiliation(s)
- Catherine Rawlinson
- Centre for Crop and Disease Management, School of Molecular and Life Sciences, Curtin University, Bentley, Western Australia, Australia.
| | - Darcy Jones
- Centre for Crop and Disease Management, School of Molecular and Life Sciences, Curtin University, Bentley, Western Australia, Australia
| | - Suman Rakshit
- Statistics for the Australian Grains Industry-West, School of Molecular and Life Sciences, Curtin University, Bentley, Western Australia, Australia
| | - Shiv Meka
- Curtin Institute for Computation, Curtin University, Bentley, Western Australia, Australia
| | - Caroline S Moffat
- Centre for Crop and Disease Management, School of Molecular and Life Sciences, Curtin University, Bentley, Western Australia, Australia
| | - Paula Moolhuijzen
- Centre for Crop and Disease Management, School of Molecular and Life Sciences, Curtin University, Bentley, Western Australia, Australia.
| |
Collapse
|
4
|
Alkhalifah Y, Phillips I, Soltoggio A, Darnley K, Nailon WH, McLaren D, Eddleston M, Thomas CLP, Salman D. VOCCluster: Untargeted Metabolomics Feature Clustering Approach for Clinical Breath Gas Chromatography/Mass Spectrometry Data. Anal Chem 2020; 92:2937-2945. [PMID: 31791122 DOI: 10.1021/acs.analchem.9b03084] [Citation(s) in RCA: 19] [Impact Index Per Article: 4.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/24/2023]
Abstract
Metabolic profiling of breath analysis involves processing, alignment, scaling, and clustering of thousands of features extracted from gas chromatography/mass spectrometry (GC/MS) data from hundreds of participants. The multistep data processing is complicated, operator error-prone, and time-consuming. Automated algorithmic clustering methods that are able to cluster features in a fast and reliable way are necessary. These accelerate metabolic profiling and discovery platforms for next-generation medical diagnostic tools. Our unsupervised clustering technique, VOCCluster, prototyped in Python, handles features of deconvolved GC/MS breath data. VOCCluster was created from a heuristic ontology based on the observation of experts undertaking data processing with a suite of software packages. VOCCluster identifies and clusters groups of volatile organic compounds (VOCs) from deconvolved GC/MS breath with similar mass spectra and retention index profiles. VOCCluster was used to cluster more than 15 000 features extracted from 74 GC/MS clinical breath samples obtained from participants with cancer before and after a radiation therapy. Results were evaluated against a panel of ground truth compounds and compared to other clustering methods (DBSCAN and OPTICS) that were used in previous metabolomics studies. VOCCluster was able to cluster those features into 1081 groups (including endogenous and exogenous compounds and instrumental artifacts) with an accuracy rate of 96% (±0.04 at 95% confidence interval).
Collapse
Affiliation(s)
| | | | | | - Kareen Darnley
- Edinburgh Cancer Centre , NHS Lothian , Edinburgh EH4 2SP , U.K
| | | | - Duncan McLaren
- Edinburgh Cancer Centre , NHS Lothian , Edinburgh EH4 2SP , U.K
| | - Michael Eddleston
- Pharmacology, Toxicology and Therapeutics Unit , University of Edinburgh , Edinburgh EH8 9YL , U.K
| | | | | |
Collapse
|
5
|
Borges H, Guibert R, Permiakova O, Burger T. Distinguishing between Spectral Clustering and Cluster Analysis of Mass Spectra. J Proteome Res 2018; 18:571-573. [PMID: 30394750 DOI: 10.1021/acs.jproteome.8b00516] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/29/2022]
Abstract
The term "spectral clustering" is sometimes used to refer to the clustering of mass spectrometry data. However, it also classically refers to a family of popular clustering algorithms. To avoid confusion, a more specific term could advantageously be coined.
Collapse
Affiliation(s)
- Hélène Borges
- Univ. Grenoble Alpes, CEA, INSERM, BIG-BGE, 38000 Grenoble , France
| | - Romain Guibert
- Univ. Grenoble Alpes, CEA, INSERM, BIG-BGE, 38000 Grenoble , France.,CNRS, BIG-BGE, F-38000 Grenoble , France
| | - Olga Permiakova
- Univ. Grenoble Alpes, CEA, INSERM, BIG-BGE, 38000 Grenoble , France
| | - Thomas Burger
- Univ. Grenoble Alpes, CEA, INSERM, BIG-BGE, 38000 Grenoble , France.,CNRS, BIG-BGE, F-38000 Grenoble , France
| |
Collapse
|
6
|
Perez‐Riverol Y, Vizcaíno JA, Griss J. Future Prospects of Spectral Clustering Approaches in Proteomics. Proteomics 2018; 18:e1700454. [PMID: 29882266 PMCID: PMC6099476 DOI: 10.1002/pmic.201700454] [Citation(s) in RCA: 13] [Impact Index Per Article: 2.2] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/21/2018] [Revised: 05/23/2018] [Indexed: 12/14/2022]
Abstract
In this article, current and future applications of spectral clustering are discussed in the context of mass spectrometry-based proteomics approaches. First of all, the main algorithms and tools that can currently be used to perform spectral clustering are introduced. In addition, its main applications and their use in current computational proteomics workflows are explained, including the generation of spectral libraries and spectral archives. Finally, possible future directions for spectral clustering, including its potential use to achieve a deeper coverage of the proteome and the discovery of novel post-translational modifications and single amino acid variants.
Collapse
Affiliation(s)
- Yasset Perez‐Riverol
- European Molecular Biology LaboratoryEuropean Bioinformatics Institute (EMBL‐EBI)Wellcome Trust Genome CampusHinxtonCambridgeCB10 1SDUK
| | - Juan Antonio Vizcaíno
- European Molecular Biology LaboratoryEuropean Bioinformatics Institute (EMBL‐EBI)Wellcome Trust Genome CampusHinxtonCambridgeCB10 1SDUK
| | - Johannes Griss
- European Molecular Biology LaboratoryEuropean Bioinformatics Institute (EMBL‐EBI)Wellcome Trust Genome CampusHinxtonCambridgeCB10 1SDUK
- Division of ImmunologyAllergy and Infectious DiseasesDepartment of DermatologyMedical University of Vienna1090ViennaAustria
| |
Collapse
|
7
|
Griss J, Perez-Riverol Y, The M, Käll L, Vizcaíno JA. Response to "Comparison and Evaluation of Clustering Algorithms for Tandem Mass Spectra". J Proteome Res 2018; 17:1993-1996. [PMID: 29682973 DOI: 10.1021/acs.jproteome.7b00824] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/21/2022]
Abstract
In the recent benchmarking article entitled "Comparison and Evaluation of Clustering Algorithms for Tandem Mass Spectra", Rieder et al. compared several different approaches to cluster MS/MS spectra. While we certainly recognize the value of the manuscript, here, we report some shortcomings detected in the original analyses. For most analyses, the authors clustered only single MS/MS runs. In one of the reported analyses, three MS/MS runs were processed together, which already led to computational performance issues in many of the tested approaches. This fact highlights the difficulties of using many of the tested algorithms on the nowadays produced average proteomics data sets. Second, the authors only processed identified spectra when merging MS runs. Thereby, all unidentified spectra that are of lower quality were already removed from the data set and could not influence the clustering results. Next, we found that the authors did not analyze the effect of chimeric spectra on the clustering results. In our analysis, we found that 3% of the spectra in the used data sets were chimeric, and this had marked effects on the behavior of the different clustering algorithms tested. Finally, the authors' choice to evaluate the MS-Cluster and spectra-cluster algorithms using a precursor tolerance of 5 Da for high-resolution Orbitrap data only was, in our opinion, not adequate to assess the performance of MS/MS clustering approaches.
Collapse
Affiliation(s)
- Johannes Griss
- Division of Immunology, Allergy and Infectious Diseases, Department of Dermatology , Medical University of Vienna , Währinger Gürtel 18-20 , Vienna 1090 , Austria.,European Molecular Biology Laboratory , European Bioinformatics Institute (EMBL-EBI) , Wellcome Trust Genome Campus , Hinxton, Cambridge CB10 1SD , United Kingdom
| | - Yasset Perez-Riverol
- European Molecular Biology Laboratory , European Bioinformatics Institute (EMBL-EBI) , Wellcome Trust Genome Campus , Hinxton, Cambridge CB10 1SD , United Kingdom
| | - Matthew The
- Science for Life Laboratory, School of Engineering Sciences in Chemistry, Biotechnology and Health , KTH - Royal Institute of Technology , Stockholm 114 28 , Sweden
| | - Lukas Käll
- Science for Life Laboratory, School of Engineering Sciences in Chemistry, Biotechnology and Health , KTH - Royal Institute of Technology , Stockholm 114 28 , Sweden
| | - Juan Antonio Vizcaíno
- European Molecular Biology Laboratory , European Bioinformatics Institute (EMBL-EBI) , Wellcome Trust Genome Campus , Hinxton, Cambridge CB10 1SD , United Kingdom
| |
Collapse
|