Spectral Library Match Assignment

spectral-library-match-assignment

Summary

Propagate spectral library match identities through candidate structures generated by in silico fragmentation using random walk algorithms to improve molecular annotation in mass spectrometry. This skill ranks candidate structures by how well they inherit spectral match confidence through fragmentation relationships.

When to use

You have a set of candidate molecular structures from in silico fragmentation (e.g., MetFrag output), a spectral library with confirmed matches to some of those structures, and you want to assign or strengthen annotations for unmatched candidates by leveraging the fragmentation graph structure. Use this when direct spectral matching is incomplete or ambiguous and you need to propagate confidence scores through molecular relationships.

When NOT to use

• Your candidate structures are already fully annotated or matched to spectra with high confidence; propagation provides marginal gains.
• You have no spectral library matches to seed the random walk; the algorithm requires at least one known positive match to begin propagation.
• Your fragmentation graph is disconnected (isolated components with no path from seeds); structures in unreachable components will receive minimal scores.

Inputs

• Candidate structures from in silico fragmentation (nodes in graph representation)
• Fragmentation relationships (edges; parent-fragment or structure-to-structure links)
• Spectral library match identities mapped to seed structures (initial known matches)
• Graph representation (edge list format: source [tab] target [tab] optional_weight)

Outputs

• Ranked candidate structures by propagated match scores
• Propagated identity scores for each candidate structure
• Personalized node ranking vector (RWR score vector w.r.t. seed nodes)

How to apply

Construct a directed graph where nodes are candidate structures and edges represent fragmentation relationships (parent → fragment). Seed the graph with spectral library match identities as initial scores on known structures. Execute a Random Walk with Restart (RWR) algorithm using pyrwr, starting from seed nodes with a restart probability (typically c=0.15) to compute personalized ranking scores across all nodes. The restart probability controls how quickly the walk decays as it moves away from seed structures—higher values keep the walk closer to seeds. Collect propagated scores for each candidate structure and rank them; structures with higher scores inherit stronger identity confidence. The output is a ranked list of candidate structures with propagated match scores, which can be used to validate or reassign molecular identities.

Related tools

• pyrwr (Executes Random Walk with Restart (RWR) algorithm to compute personalized node ranking scores across the fragmentation graph; supports GPU acceleration and multiple seed types (RWR, PPR, PageRank).) — https://github.com/jinhongjung/pyrwr
• MetFrag (Generates candidate structures via in silico fragmentation; produces the structure graph and initial candidate list that seeds the propagation workflow.) — https://ipb-halle.github.io/MetFrag/projects/metfragcl/
• ChemWalker (Python package integrating in silico fragmentation (MetFrag), spectral library matching, and random walk propagation; orchestrates the full skill workflow.) — https://github.com/computational-chemical-biology/chemwalker

Examples

from pyrwr.rwr import RWR; rwr = RWR(); rwr.read_graph('fragmentation_graph.tsv', 'directed'); scores = rwr.compute(seed=10982, c=0.15, epsilon=1e-9, max_iters=100)

Evaluation signals

• Verify graph connectivity: all seed structures appear in the input edge list and have outgoing or incoming edges; disconnected seed components should be flagged.
• Check RWR score distribution: scores should decay from seed nodes; verify that structurally distant nodes have lower scores than nearby nodes.
• Validate score normalization: propagated scores should sum to or be bounded by the total initial seed score; scores ≤ 1.0 indicate proper probability-like behavior.
• Compare rankings before and after propagation: newly ranked high-scoring structures should be structurally related (nearby in fragmentation graph) to seed matches.
• Consistency check: re-running the same query with identical parameters should produce identical output scores (deterministic within numerical precision).

Limitations

• RWR propagation requires well-connected fragmentation graphs; sparse or fragmented graphs will limit score propagation to isolated regions.
• Restart probability (c) is a tuning parameter; too high (c → 1) keeps walks near seeds (low propagation), too low (c → 0) diffuses scores uniformly (loss of seed bias). Default c=0.15 was not empirically validated for all chemical spaces in the README.
• Spectral library match quality directly affects seed quality; poor or incorrect initial matches will propagate false identities throughout the graph.
• The algorithm assumes fragmentation relationships are symmetric or correctly directed; incorrect edge orientation can reverse or invalidate propagation flow.
• Computationally expensive on very large graphs (millions of nodes/edges); GPU acceleration (via pyrwr) helps but requires compatible hardware.

Evidence

• [readme] ChemWalker is a python package to propagate spectral library match identities through candidate structures provided by in silico fragmentation, using random walk: "ChemWalker is a python package to propagate spectral library match identities through candidate structures provided by in silico fragmentation, using random walk"
• [other] Load candidate structures from in silico fragmentation as a graph representation (nodes=structures, edges=fragmentation relationships). Load spectral library matches as seed identities mapped to initial structures. Initialize a random walk engine using pyrwr with the candidate structure graph. Execute random walk propagation starting from seed nodes (spectral matches) to propagate identity scores through the graph.: "Load candidate structures from in silico fragmentation as a graph representation (nodes=structures, edges=fragmentation relationships). Load spectral library matches as seed identities mapped to"
• [readme] Random Walk with Restart (RWR) is one of famous link analysis algorithms, which measures node-to-node proximities in arbitrary types of graphs (networks).: "Random Walk with Restart (RWR) is one of famous link analysis algorithms, which measures node-to-node proximities in arbitrary types of graphs (networks)."
• [readme] pyrwr aims to implement algorithms for computing RWR scores based on Power Iteration using numpy and scipy in Python. More specifically, pyrwr focuses on computing a single source RWR score vector w.r.t. a given query (seed) node: "pyrwr focuses on computing a single source RWR score vector w.r.t. a given query (seed) node, which is used for a personalized node ranking w.r.t. the querying node."
• [readme] c: Restart probablity (rwr) or jumping probability (otherwise): "c: Restart probablity (rwr) or jumping probability (otherwise)"