Spectrum vector similarity searching

spectrum-vector-similarity-searching

Summary

Efficiently retrieve k nearest neighbors for each spectrum vector using spatial indexing structures (k-d trees, LSH-based inverted indexes) to enable sparse pairwise distance computation without exhaustive all-vs-all comparisons. This skill is critical for scaling spectrum clustering to millions of MS/MS spectra.

When to use

When clustering large collections (thousands to millions) of tandem mass spectra and you need to compute a sparse pairwise distance matrix for density-based clustering. Specifically, use this skill after spectrum vectors have been converted to low-dimensional representations via feature hashing, and you must avoid the O(n²) cost of comparing every spectrum to every other spectrum.

When NOT to use

• Input spectra have not yet been converted to low-dimensional vectors via feature hashing; preprocessing is required first.
• Clustering dataset is small (< 1000 spectra) where exhaustive all-vs-all comparison is computationally acceptable.
• You require dense pairwise distance computation (all spectrum pairs) rather than sparse similarity; use exhaustive cosine distance instead.

Inputs

• spectrum vectors (low-dimensional, hashed representations derived from binned high-resolution MS/MS spectra)
• precursor m/z values (for bucketing and nearest neighbor index construction)
• k parameter (number of nearest neighbors to retrieve per spectrum)

Outputs

• sparse pairwise distance matrix (cosine distance between each spectrum and its k nearest neighbors)
• nearest neighbor index structure (Voronoi diagram with inverted index for future queries)

How to apply

Construct nearest neighbor indexes from spectrum vectors by partitioning them into buckets (typically by precursor m/z) and building a Voronoi diagram with an inverted index structure. Query each spectrum vector against the index to retrieve its k nearest neighbors (controlled by n_neighbors and n_probe parameters). Compute pairwise distances only between each spectrum and its retrieved neighbors, storing results in sparse matrix format. The trade-off between speed and accuracy is governed by n_probe (number of inverted index lists to inspect) and low_dim (length of low-dimensional vectors); higher values increase accuracy at the cost of computation time.

Related tools

• falcon (spectrum clustering tool that constructs and queries nearest neighbor indexes to compute sparse pairwise distance matrices and perform density-based clustering) — https://github.com/bittremieux/falcon
• spectrum-utils (utility library for spectrum preprocessing and manipulation, integrated as a dependency for spectrum vector construction)

Examples

falcon peak/*.mzml falcon --export_representatives --precursor_tol 20 ppm --fragment_tol 0.05 --eps 0.10

Evaluation signals

• Sparse distance matrix is populated only for spectrum pairs within the retrieved k nearest neighbors; verify sparsity ratio matches expected density for chosen k and dataset size.
• Nearest neighbor index construction completes without error and memory usage scales with bucketed partitions rather than O(n²) full distance matrix.
• Cosine distances in sparse matrix fall within expected range [0, 2] and respect precursor m/z tolerance (precursor_tol constraint) when index was bucketed by precursor mass.
• Downstream density-based clustering (DBSCAN) produces cluster assignments that are stable under small changes to eps threshold, indicating the sparse distance matrix accurately captured spectrum similarity structure.
• Retrieved nearest neighbors have cosine similarity (1 - cosine_distance) that is consistent with true similarity; verify by spot-checking against exhaustive computation on a subset.

Limitations

• Accuracy depends on exploration depth (n_probe): inspecting fewer inverted index lists runs faster but risks missing true nearest neighbors in high-dimensional space.
• Low-dimensional vector length (low_dim) trades off accuracy against memory and query speed; shorter vectors approximate true cosine distance less accurately.
• Performance is sensitive to bucketing strategy (e.g., by precursor m/z): poor bucket separation may lead to sparse index and missed neighbors.
• LSH-based indexes are probabilistic and may occasionally fail to retrieve a true nearest neighbor; increasing n_probe reduces but does not eliminate this risk.
• Settings are tuned for bottom-up proteomics data (minimum 5 peaks, 250 m/z range, 101–500 m/z window); metabolomics and top-down data may require adjusted preprocessing (min_peaks, min_mz_range, scaling).

Evidence

• [intro] Nearest neighbor indexes enable sparse distance computation: "The nearest neighbor indexes are used to efficiently compute a sparse pairwise distance matrix without having to exhaustively compare all spectra to each other."
• [readme] Index construction from spectrum vectors via Voronoi partitioning: "The spectrum vectors in each bucket are partitioned into data subspaces to create a Voronoi diagram, and all vectors are assigned to their nearest representative vector in an inverted index."
• [readme] Accuracy vs speed trade-off via probe and neighbor parameters: "The accuracy and speed of similarity searching is governed by the number of neighboring cells to explore during searching: exploring more cells during searching decreases the chance of missing a"
• [readme] n_probe and low_dim tuning guidance: "n_probe: The maximum number of lists in the inverted index to inspect during querying. Inspecting fewer lists will run faster but will give slightly less accurate clustering results. low_dim: The"
• [readme] Bucketing by precursor m/z for index construction: "Vectors are split into buckets based on the precursor m/z of the corresponding spectra to construct nearest neighbor indexes for highly efficient spectrum comparison."