Laplacian Embedding Spectral Alignment

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."