Beyond Delta Masses: MS Andrea Directly Resolves Combinatorial Peptide Modifications in Open Searches

The paper introduces MS Andrea, a novel open modification search engine that directly identifies and scores combinations of up to four variable modifications per peptide at the PSM level without predefined lists, achieving superior identification rates and enhanced interpretability compared to existing tools like MSFragger and Sage.

The Gist

Imagine you are a detective trying to solve a mystery inside a massive, chaotic library. This library is your proteome (the collection of all proteins in a cell). The books are proteins, but they often come with sticky notes, coffee stains, or even whole new chapters attached to them. These are called modifications (like phosphorylation), and they change how the protein works.

The problem is that these sticky notes are often unexpected. You don't know exactly what they are or where they are placed.

The Old Way: The "Mass Difference" Detective

For a long time, the detectives (software tools like MSFragger and Sage) used a clever but limited method. They would look at a book (a peptide) and measure how much heavier it was than the original version in the catalog.

• The Analogy: Imagine you find a book that weighs 100 grams more than the catalog says it should. The old detectives would say, "Aha! This book has a 100g mystery weight attached to it."
• The Problem: They would stop there. They wouldn't tell you what that 100g was. Was it one heavy stone? Two medium bricks? Or four tiny gold coins? The detective would hand you the book and say, "Good luck figuring out what those 100 grams are." You had to use other tools or guesswork to decode the mystery later.

The New Hero: MS Andrea

The authors of this paper introduced a new detective named MS Andrea. MS Andrea is special because it doesn't just measure the weight; it actually unpacks the mystery right there at the crime scene.

Here is how MS Andrea solves the case, using simple steps:

1. The "Fingerprint" Search (Sequence Tags)

Before looking at the whole library, MS Andrea looks for small, unique patterns in the book's text (called sequence tags).

• Analogy: Instead of reading every single word in a library of millions of books, MS Andrea looks for a specific phrase like "The quick brown fox." If a book contains that phrase, it's a candidate. This filters out millions of irrelevant books instantly, saving time.

2. The "Weight" Check

Once it has a shortlist of candidate books, it checks the total weight again.

• The Old Way: "This book is 100g heavier. It's a match."
• MS Andrea's Way: "This book is 100g heavier. Let's see... could that be one 50g stone and two 25g stones? Or maybe four 25g stones?"

3. The "Combinatorial" Magic (The Big Breakthrough)

This is where MS Andrea shines. Most other detectives can only guess if there is one or two mystery items attached. MS Andrea is smart enough to try combinations of up to four different items at once.

• Analogy: Imagine you have a scale. The old detectives try to balance it with one or two heavy objects. MS Andrea is like a master chef who can perfectly balance the scale using a complex recipe of up to four different ingredients (modifications) to match the exact weight difference.

Why Does This Matter?

1. No More Guessing: MS Andrea tells you exactly what the modifications are and where they are on the protein. It doesn't just say "100g mystery"; it says, "There is a Phosphorylation on the 3rd letter and another on the 12th letter."
2. Finding the Hidden Gems: Because it can handle up to four modifications at once, it finds proteins that other tools miss. If a protein has three or four sticky notes, the old tools might get confused and give up. MS Andrea stays calm and solves the puzzle.
3. Speed: Even though it does more work, it's fast because it uses those "fingerprint" filters to ignore the books that don't matter.

The Results

The authors tested MS Andrea on two different "libraries" (cells from human tissue and plants).

• The Score: MS Andrea found the most matches (Peptide-Spectrum Matches) compared to the other top detectives.
• The Detail: While the other tools found similar numbers of books, MS Andrea found more versions of those books because it could identify the complex combinations of sticky notes that the others ignored.

In a Nutshell

If the other search engines are like a scale that tells you "Something is wrong with the weight," MS Andrea is like a forensic scientist who opens the package, identifies every single item inside, and tells you exactly what they are and where they belong. It turns a vague "mass difference" into a clear, detailed story about the protein's modifications.

Technical Summary

1. Problem Statement

Open Modification Search (OMS) strategies have become essential in mass spectrometry-based proteomics for identifying peptides with unknown or unexpected post-translational modifications (PTMs). However, current state-of-the-art OMS engines (e.g., MSFragger, Sage) suffer from a critical limitation:

• Delta Mass Reporting: They primarily report only the overall mass difference ($\Delta$mass) between the precursor ion and the matched peptide sequence.
• Lack of Explicit Scoring: They do not explicitly identify, score, or localize specific combinations of multiple modifications at the Peptide-Spectrum Match (PSM) level.
• Downstream Dependency: Interpreting the nature and location of these mass shifts requires end-users to rely on separate downstream tools (e.g., PTM-Shepherd) to infer modification identities.
• Combinatorial Limits: Existing tools often struggle to robustly score peptides carrying more than one or two variable modifications simultaneously due to the combinatorial explosion of candidate peptides.

2. Methodology: MS Andrea Algorithm

MS Andrea is a novel OMS search engine designed to directly identify and score combinations of up to four variable modifications per peptide without predefining them. The algorithm employs a multi-stage workflow to manage the large search space:

A. Pre-processing and Peak Picking

• Deconvolution: Spectra undergo deisotoping and charge reduction (up to 3+ charge states).
• Precursor-Dependent Peak Picking: To balance information content and noise, the number of peaks selected per 100 m/z window varies based on precursor mass:
  • $\ge$ 1000 Da: Top 3 peaks.
  • 700–1000 Da: Top 5 peaks.
  • < 700 Da: All peaks (up to 25).
• Auxiliary Peaks: Specific masses (e.g., proton, water, precursor mass) are added based on the fragmentation method (b/y-ions) to assist in tag generation.

B. Sequence Tag Extraction (Filtering Stage 1)

• Graph-Free Approach: Instead of constructing a full spectrum graph, MS Andrea identifies "edges" between peaks where the mass difference corresponds to one or two amino acid residues.
• Tag Construction: It generates sequence tags of 2, 3, or 4 amino acids.
  • Double Edges: If a mass difference matches two residues, the order is ambiguous; the algorithm generates edges for both permutations (e.g., "VS" and "SV").
  • Constraints: Valid tags allow at most one "double edge" per tag to maintain reliability.
• Candidate Filtering: The database is filtered to retain only peptides containing at least one 3- or 4-residue tag (or two 2-residue tags). This drastically reduces the candidate pool before scoring.
• Mass Tolerance: A wide MS1 tolerance (-500 Da to +1 Da) is applied to accommodate potential variable modifications.

C. Two-Stage Scoring

1. Fixed Modification Scoring: Remaining candidates are scored using the MS Amanda scoring function considering only fixed modifications. The top 10 scoring candidates are retained.
2. Variable Modification Scoring (Main Stage):
   • The algorithm calculates the mass difference ($\Delta$mass) between the precursor and the matched peptide.
   • It generates all possible combinations of up to four modifications from the Unimod database that sum to this $\Delta$mass.
   • Each candidate peptide is re-scored against the spectrum with these specific modification combinations applied.
   • The final score is the maximum score achieved across all valid modification combinations.

3. Key Contributions

• Direct PSM-Level Resolution: Unlike competitors, MS Andrea outputs the specific identity, mass, and localization of modifications directly in the PSM results, eliminating the need for post-hoc interpretation tools for basic identification.
• High-Order Combinatorial Scoring: It is capable of scoring and localizing peptides with up to four simultaneous variable modifications, a capability often limited or absent in other OMS engines.
• Efficient Search Space Reduction: The use of sequence tags as a pre-filtering mechanism allows for efficient handling of the vast search space inherent in open searches without sacrificing sensitivity.
• Open Source Availability: The tool is implemented in C# and is freely available as a command-line interface for Windows, Linux, and macOS.

4. Results

The authors evaluated MS Andrea using phosphorylated peptide datasets from HeLa cells and Arabidopsis thaliana, comparing it against MSFragger and Sage.

• PSM Identification Rates:
  • At a 1% False Discovery Rate (FDR), MS Andrea identified the highest number of PSMs in both datasets.
  • HeLa Dataset: MS Andrea achieved 6,100 PSMs (STDA) and ~8,300 PSMs (with Percolator), outperforming MSFragger (5,200 STDA / 6,700 Percolator) and Sage (1,500 STDA).
• Peptide-Level Overlap:
  • There was a high consensus in identified peptide sequences between the engines (e.g., ~2,730 shared peptides in HeLa Rep 1).
  • However, MS Andrea identified more unique peptides (707) compared to MSFragger (486) and Sage (~691), suggesting it captures distinct peptidoforms.
• Modification Localization:
  • Table 1 Analysis: For top-scoring PSMs, MS Andrea correctly identified specific phospho-sites (e.g., S1, T9, T11). In contrast, MSFragger only provided a localization score for the total mass shift, requiring external tools to interpret the specific residue.
  • Table 2 Analysis: MS Andrea successfully identified peptides with three variable modifications (e.g., three phosphorylation sites). In several cases, MSFragger and Sage either failed to identify the target peptide or assigned it as a decoy, whereas MS Andrea provided a high-scoring target hit.

5. Significance

• Enhanced Interpretability: By resolving the "delta mass" into specific modification identities and sites at the PSM level, MS Andrea significantly reduces the burden on researchers to manually interpret complex modification patterns.
• Discovery of Complex PTMs: The ability to score up to four modifications simultaneously allows for the detection of highly modified peptides that are often missed or misidentified by engines restricted to fewer variable modifications.
• Competitive Performance: MS Andrea maintains competitive (and often superior) identification sensitivity compared to established engines like MSFragger, proving that explicit multi-modification scoring does not come at the cost of search speed or accuracy.
• Future Integration: The authors plan to integrate MS Andrea into the Thermo Fisher Proteome Discoverer software, which will facilitate broader adoption in the proteomics community.

In conclusion, MS Andrea represents a significant advancement in OMS by shifting the paradigm from reporting "mass shifts" to reporting "specific modified peptides," thereby enabling more detailed and interpretable characterization of the proteome.