Scalable mass-spectrometry-based molecular phylogeny with TreeMS2

The paper introduces TreeMS2, a scalable and annotation-independent computational framework that constructs molecular phylogenies directly from raw mass spectrometry data to reveal evolutionary relationships and functional adaptations across proteomic and metabolomic phenotypes.

The Gist

Imagine you are trying to figure out how different people are related to each other. Traditionally, scientists do this by looking at their DNA—the biological instruction manual written in the code of life. It's like comparing the blueprints of two houses to see if they were built by the same architect.

But what if you wanted to know how similar two people are based on what they are actually doing right now? What if you looked at their clothes, their cooking style, or the tools they use in their workshop? This is the "realized phenotype"—the actual, living result of their biology interacting with their environment.

This paper introduces a new tool called TreeMS2 that does exactly this, but for microscopic molecules. Instead of reading the DNA blueprints, TreeMS2 looks at the "fingerprint" of molecules (proteins and metabolites) floating inside an organism using a machine called a Mass Spectrometer.

Here is a simple breakdown of how it works and why it's a big deal:

1. The Problem: The "Library" is Too Big

Imagine you have a library with billions of books (mass spectrometry data), but most of them are written in a language you don't speak, and the titles are missing.

• Old Way: Scientists tried to read every book, translate the words (identify the specific molecules), and then compare them. This is slow, expensive, and if the library has books about alien life that don't exist in our dictionaries, the old methods just give up.
• The Bottleneck: Comparing every book to every other book one by one takes forever. If you have a million books, the math gets so heavy that computers crash.

2. The Solution: TreeMS2 (The "Blind" Matchmaker)

TreeMS2 is a new, super-fast computer program that skips the translation step entirely. It doesn't care what the molecules are named; it only cares about their shape and pattern.

• The Analogy: Imagine you have two piles of puzzle pieces.
  • Old Method: You try to read the picture on every single piece to see if they fit.
  • TreeMS2 Method: You just look at the jagged edges of the pieces. If the edges of a piece from Pile A fit perfectly with a piece from Pile B, you know the piles are related. You do this by looking at the "edges" (the mass spectrometry spectra) of millions of pieces in seconds.

3. How It Works (The Magic Trick)

TreeMS2 uses a few clever tricks to be fast:

• Vectorization: It turns the complex data of a molecule into a simple list of numbers (like a barcode).
• The "Speed Search": Instead of comparing every single molecule to every other single molecule (which would take years), it uses a "smart search" (approximate nearest-neighbor). It's like asking a librarian, "Find me books that look like this one," rather than reading every book in the library to find the match.
• The Result: It creates a Distance Map. If two samples have very similar molecular "fingerprints," they are placed close together on the map. If they are different, they are far apart.

4. What Did They Discover? (The Proof)

The team tested TreeMS2 on four very different types of data, and it worked like a charm:

• Bacteria (The Family Tree): They analyzed 303 types of bacteria. TreeMS2 built a family tree that perfectly matched the known evolutionary history, proving that molecular "fingerprints" reflect evolutionary relationships.
  • The Bonus: It also caught a mistake! Some bacteria samples were accidentally swapped in the lab. TreeMS2 spotted them because they looked like the wrong family, acting like a quality-control detective.
• The "Kingdom of Life" (The Big Picture): They tested viruses, archaea, bacteria, and complex animals (like humans and plants). Even though the data was huge (millions of molecules), TreeMS2 correctly grouped viruses together, bacteria together, and animals together, showing it can handle the whole tree of life.
• Single Cells (The Tiny Details): They looked at individual human stem cells. Even though the data was very "noisy" (like trying to hear a whisper in a storm), TreeMS2 could tell the difference between a stem cell and a developing cell, showing it works even on tiny, messy samples.
• Food (The Grocery Store): They analyzed over 3,500 food items (meat, fruits, dairy, etc.). The tool automatically grouped all the meats together, all the fruits together, and even noticed that fermented foods (like yogurt) were distinct from their non-fermented cousins (like milk). It did this without needing to know the chemical name of every ingredient.

Why This Matters

TreeMS2 is a game-changer because it is scalable and blind.

• Scalable: It can handle data sets that are millions of times bigger than what previous tools could manage.
• Blind: It doesn't need a dictionary. It can analyze organisms we've never seen before or molecules we can't name yet.

In a nutshell: TreeMS2 is like a super-fast, universal translator that doesn't need to know the words to understand the story. It looks at the raw patterns of life's building blocks to tell us who is related to whom, what is healthy, and where mistakes happened, all without needing to read the genetic code first. It opens the door to exploring the "molecular phenotype" of life on a scale we've never seen before.

Technical Summary

1. Problem Statement

Molecular phylogeny has traditionally relied on DNA and RNA sequences to infer evolutionary relationships. While mass spectrometry (MS) generates vast repositories of proteomic and metabolomic data representing the "realized molecular phenotype," these datasets remain largely untapped for phylogenetic analysis.

• Limitations of Current Methods: Existing tools like compareMS2 (proteomics) and Qemistree (metabolomics) suffer from critical limitations:
  • Scalability: compareMS2 relies on exhaustive pairwise comparisons, resulting in quadratic computational complexity ($O(N^2)$), making it intractable for large datasets (millions of spectra).
  • Annotation Dependency: Qemistree requires in silico annotation (e.g., via SIRIUS/CSI:FingerID) to generate molecular fingerprints. This fails for unannotated spectra, which are common in large public datasets, environmental samples, and non-model organisms.
• The Gap: There is no scalable, annotation-independent framework capable of reconstructing phylogenies directly from raw MS/MS data across diverse omics modalities (proteomics, metabolomics, single-cell).

2. Methodology: TreeMS2

TreeMS2 is a computational framework designed to construct similarity matrices and phylogenetic trees directly from raw tandem mass spectrometry (MS/MS) spectra without requiring molecular identification.

Core Workflow:

1. Spectral Vectorization:
   • Raw MS/MS spectra are preprocessed (noise removal, peak filtering, intensity scaling, L2-normalization).
   • Spectra are converted into high-dimensional sparse vectors by binning fragment $m/z$ values (default tolerance: 0.05 $m/z$).
2. Dimensionality Reduction:
   • Sparse random projections are applied to reduce dimensionality while preserving cosine similarity, generating dense vectors (default size: 400).
3. Approximate Nearest Neighbor (ANN) Search:
   • Vectors are stored in Lance vector stores, partitioned by precursor charge to restrict comparisons to similar fragmentation patterns.
   • Indexing: Depending on dataset size, TreeMS2 uses:
     • Flat exhaustive search (small datasets).
     • Inverted File (IVF) indexes with k-means centroids.
     • Hierarchical Navigable Small World (HNSW) graphs for very large datasets ($\ge$1M vectors).
   • This reduces computational complexity from quadratic to near-linear scaling.
4. Similarity Calculation:
   • For each spectrum in Sample A, the system searches for the top $N$ nearest neighbors in Sample B.
   • Sample-to-sample similarity is defined as the average fraction of spectra in one sample that have at least one close match (above a similarity threshold, e.g., 0.8) in the other.
5. Output:
   • A symmetric distance matrix is generated, compatible with standard phylogenetic tools (e.g., MEGA for UPGMA trees) and dimensionality reduction techniques (UMAP, MDS).

Key Technical Innovations:

• Annotation Independence: Operates entirely on raw spectral content, bypassing the need for peptide/protein/metabolite identification.
• Scalability: Handles datasets with hundreds of millions of spectra (e.g., 56M spectra processed in <13 hours).
• Modality Agnostic: The same pipeline applies to proteomics (DDA/DIA), single-cell proteomics, and untargeted metabolomics with minor parameter adjustments.

3. Key Contributions

• TreeMS2 Software: An open-source tool (GitHub: bittremieuxlab/TreeMS2) enabling large-scale, annotation-free phylogenetic analysis.
• Algorithmic Efficiency: Introduction of sparse random projections and ANN indexing to solve the scalability bottleneck of spectral comparison.
• Unified Framework: A single method capable of analyzing proteomics, metabolomics, and single-cell data, bridging the gap between genetic and phenotypic evolutionary studies.

4. Results and Validation

The authors validated TreeMS2 across four diverse use cases:

A. Bacterial Proteomics (Taxonomy Recovery & QC)

• Dataset: 303 bacterial proteomes (13M spectra).
• Performance: Processed in <3.5 hours (compareMS2 failed to complete).
• Outcome: The derived tree recapitulated established taxonomy (Phylum to Genus level) with high correlation (Mantel $\rho = 0.665$).
• Anomaly Detection: Successfully identified sample handling errors (e.g., mislabeled Pseudomonas wells) where samples clustered with the wrong species. Re-annotation of these "outlier" samples against the correct neighbor database drastically improved identification rates (e.g., from 0.5% to 21%), confirming the method's utility for automated quality control.

B. Kingdom of Life Proteomics

• Dataset: 79 species across viruses, archaea, bacteria, and eukaryotes (56M spectra).
• Outcome: The phylogeny matched NCBI taxonomy (46% of first neighbors matched).
• Insight: Detected biological anomalies, such as Dictyostelium discoideum clustering with E. coli due to dietary contamination (food source), and Mycoplasma clustering closer to viruses due to functional similarities (lack of cell wall, small genome).

C. Single-Cell Proteomics (SCP)

• Dataset: Human iPSCs and embryoid body cells (20M spectra, DIA data).
• Outcome: Successfully distinguished cell types and differentiation trajectories despite high noise, sparsity, and missing values.
• Significance: Demonstrated that raw spectral similarity can resolve biological structure in SCP data where traditional peptide quantification tables are often too sparse or noisy.

D. Global Food Metabolomics

• Dataset: 3,500 food samples (4M spectra, untargeted metabolomics).
• Outcome: UMAP embeddings revealed clear clustering by food category (meat, seafood, dairy, plants) and sub-structure (e.g., fermented vs. non-fermented, alcohol content).
• Significance: Proved the method's ability to capture biochemical diversity without relying on metabolite annotation, which is often low in untargeted studies.

5. Significance and Impact

• Bridging Genotype and Phenotype: TreeMS2 allows researchers to compare evolutionary relationships based on the functional molecular phenotype (proteome/metabolome) against genetic history, revealing convergent evolution, niche specialization, and environmental adaptation.
• Scalability for Big Data: It unlocks the potential of public MS repositories (PRIDE, GNPS, MassIVE) containing billions of spectra, which were previously computationally inaccessible for phylogenetic analysis.
• Robust Quality Control: The method provides an unsupervised mechanism to detect sample mix-ups, contamination, and low-quality runs directly from raw data.
• Domain Agnosticism: By removing the dependency on reference databases, TreeMS2 is particularly powerful for studying non-model organisms, environmental samples, and natural products where reference libraries are incomplete.

In conclusion, TreeMS2 establishes a new paradigm for "sequence-free phylogenetics," offering a scalable, unbiased, and robust framework for exploring molecular relationships across the tree of life and diverse chemical spaces.