Laplacian Embedding Spectral Alignment

---
name: laplacian-embedding-spectral-alignment
description: Use when you have two or more MS/MS fragmentation spectra (with precursor
  m/z, fragment m/z values, and intensities) and need to identify which fragment ions
  match across spectra while quantifying the statistical confidence of those matches.
license: CC-BY-4.0
metadata:
  edam_operation: http://edamontology.org/operation_3631
  edam_topics:
  - http://edamontology.org/topic_3520
  - http://edamontology.org/topic_0121
  tools:
  - SIMILE
  - Python
  techniques:
  - LC-MS
  license_tier: open
  provenance_tier: literature
derived_from:
- doi: 10.1038/s41467-022-30118-9
  title: SIMILE
evidence_spans:
- SIMILE (Significant Interrelation of MS/MS Ions via Laplacian Embedding) is a Python
  library
- is a Python library for interrelating fragmentation spectra with significance estimation
claims: []
provenance:
  collection: https://w3id.org/holobiomicslab/asb-skill/collection/metabolomics/v2
  assembled_by: scripts/collect_metabolomics_collection.py
  sources:
  - build: coll_simile_cq
    doi: 10.1038/s41467-022-30118-9
    title: SIMILE
  dedup_kept_from: coll_simile_cq
schema_version: 0.2.0
attribution:
  generator: AgenticScienceBuilder
  original_doi: 10.1038/s41467-022-30118-9
  all_source_dois:
  - 10.1038/s41467-022-30118-9
  zenodo_doi: 10.5281/zenodo.20794027
  curators: []
  promoter: Louis-Félix Nothias
  sponsor: CNRS & Université Côte d'Azur
---

# laplacian-embedding-spectral-alignment

## Summary

Apply Laplacian embedding to compute fragment ion similarity and statistical significance when aligning pairs of MS/MS fragmentation spectra. This skill captures both local mass difference patterns (shortest-path distance) and global spectral graph structure (average commute time) to enable robust matching across chemical structure variants.

## When to use

You have two or more MS/MS fragmentation spectra (with precursor m/z, fragment m/z values, and intensities) and need to identify which fragment ions match across spectra while quantifying the statistical confidence of those matches. Use this skill when simple mass tolerance-based matching is insufficient and you need to account for structural relationships between fragment ions (ancestors, descendants, and siblings).

## When NOT to use

- Input spectra contain fewer than 3–4 fragment ions per spectrum; Laplacian embedding requires sufficient graph structure to capture meaningful ancestor/descendant relationships.
- You only need simple binary present/absent matching without significance estimation; use naive mass tolerance filtering instead.
- Fragment ions are already grouped into known chemical families; Laplacian embedding is designed to discover these relationships de novo from mass differences.

## Inputs

- MS/MS fragmentation spectrum pair (precursor m/z, fragment m/z array, intensity array for each spectrum)
- Mass tolerance (ppm or Da) for m/z difference matching
- Optional: precursor-based neutral loss counts

## Outputs

- Matching ions report (tabulated fragment pairs with alignment scores, mass deltas, p-values/Z-scores, and metadata)
- Similarity matrix (S) of fragment ion relationships
- Maximum weight matching matrix (M)
- Comparison matrix (C) indicating symmetric (1) vs. asymmetric (-1) matches
- Spectral similarity scores with p-values and null distribution

## How to apply

First, parse the two input MS/MS spectra to extract precursor mass, fragment m/z values, and intensities. Compute a similarity matrix from pairwise mass differences (m/z deltas) between all fragment ion pairs across the two spectra using row-normalized transition probabilities of mass difference frequencies. Convert this transition matrix to the pseudo-inverse of its normalized Laplacian, which captures both shortest-path distance (property a: common mass differences) and average commute time distance (property b: structural relatedness through ancestors and descendants). Apply maximum weight matching to identify the optimal set of fragment ion pairs that maximize alignment score. Finally, perform statistical significance testing via z-test on the matched pairs using a null distribution generated by permuting intra- and inter-spectral fragment similarity scores, yielding p-values or Z-scores for each match.

## Related tools

- **SIMILE** (Python library implementing Laplacian embedding similarity matrix construction, maximum weight matching, and z-test significance calculation for fragment ion alignment) — https://github.com/biorack/simile
- **Python** (Runtime environment; SIMILE depends on numpy, scipy, and pandas for matrix operations and statistical testing)

## Examples

```
import simile as sml; S, spec_ids = sml.similarity_matrix(mzs, pmzs=pmzs, tolerance=0.1); M = sml.multiple_match(S, spec_ids); C = sml.sym_compare(M, spec_ids); spec_scores, pval, null_dist = sml.z_test(S, M, C, spec_ids, return_dist=True); df = sml.matching_ions_report(S, M, C, mzs, pmzs)
```

## Evaluation signals

- Matched fragment pairs report is non-empty and each pair has a mass delta consistent with known neutral losses or fragment fragmentation pathways (e.g., 18 Da for H₂O loss, 44 Da for CO₂).
- Symmetric matches (C = 1) outnumber asymmetric matches (C = −1) for true positive alignments; p-values for symmetric matches are significantly smaller than for random permutations.
- Z-scores and p-values follow expected distributions under the null hypothesis (histogram of p-values is uniform [0, 1] for true negatives, left-skewed for true positives).
- Maximum weight matching output includes all high-confidence fragment pairs identified by manual or reference spectral libraries; no expected pairs are missing.
- Null distribution generated by permutation is visibly distinct from observed spectral similarity scores, confirming that the matching is not due to chance.

## Limitations

- Laplacian embedding requires sufficient fragmentation complexity (minimum ~3–4 fragment ions per spectrum); sparse spectra may yield unreliable significance estimates.
- The method assumes that fragment ion similarity is driven by mass difference frequency and structural graph properties; it may fail for non-standard fragmentation pathways or heavily modified peptides where mass differences are atypical.
- Multiple comparison correction is required when testing many spectrum pairs simultaneously; the README notes that 'current research in multiple comparison is exploring using the asymmetry of the SIMILE max weight matrix as an alternative'.
- Python 3.7 pinning due to non-SIMILE bugs may limit compatibility with newer dependency versions.

## Evidence

- [readme] Fragment ions are similar if the difference in mass between them is common.: "Fragment ions are similar if the difference in mass between them is common."
- [readme] Fragment ions are similar if their ancestor and descendent fragment ions are similar.: "Fragment ions are similar if their ancesetor and descendent fragment ions are similar."
- [readme] This corresponds to an 'average commute time' distance between fragment ions with the following intuition: If instead of taking the shortest path between x and y we instead meander about according to the transition matrix, how long will it take to wander from x to y and back to x on average?: "This corresponds to an 'average commute time' distance between fragment ions with the following intuition: If instead of taking the shortest path between x and y we instead meander about according to"
- [intro] Maximum weight matching is used instead of original monotonic alignment method with improved performance.: "Maximum weight matching is used instead of original monotonic alignment method with improved performance"
- [readme] Taking this line of reasoning to its natural conclusion yields a null distibution generated by permuting intra and inter spectral fragment similarity scores to yield p-values.: "Taking this line of reasoning to its natural conclusion yields a null distibution generated by permuting intra and inter spectral fragment similarity scores to yield p-values."
- [other] Compute pairwise mass differences (m/z deltas) between all fragment ions across the two spectra.: "Compute pairwise mass differences (m/z deltas) between all fragment ions across the two spectra."
- [other] Generate a matching ions report tabulating all matched fragment pairs, their scores, mass deltas, and significance metrics with associated metadata.: "Generate a matching ions report tabulating all matched fragment pairs, their scores, mass deltas, and significance metrics with associated metadata."