Wild-AC: A fast, index-free multi-pattern string matching algorithm with wildcard support for proteomics.
- 1Institut für Mathematik und Informatik, Freie Universität Berlin, Takustr. 9, 14195, Berlin, Germany. [email protected].
Abstract
Background
Efficient multi-pattern string matching with wildcard support is essential in proteomics, where peptides must be mapped to protein databases containing ambiguous amino acids (e.g., B, Z, X). Existing approaches either require preprocessing (e.g., FM-index) or fail to handle wildcards in the text.Results
We present Wild-AC, a modified Aho-Corasick algorithm that supports wildcards in the text by branching the search into parallel 'scout' paths, one per possible wildcard representation, while the unmodified primary search continues unaffected in the common, wildcard-free case. Wild-AC outperforms the FM-index (wildcard case) and matches or exceeds Wu-Manber (exact search) in speed for realistic proteomics workloads, i.e., 1000-500 000 peptide patterns (average length ∼18 amino acids) searched against protein databases (texts) of 3 × 10⁶-2.1 × 10⁸ characters. On databases masked to a wildcard rate of 5%, Wild-AC retains its advantage for large peptide sets, while the FM-index becomes preferable for small ones. It requires no index, scales well with pattern count, and supports multi-threading. The C++ implementation is open source at https://github.com/Wild-AC/Wild-AC .Conclusion
Wild-AC extends the Aho-Corasick algorithm to support wildcards and outperforms FM-Index and Wu-Manber in the task of peptide-protein mapping while considering ambiguous amino acids.
Related
- Identifying Differentially Expressed Proteins via Plasma Exosomal Proteomics
- Integrated Spatial Metabolomics and Proteomics from the Same Tissue Section Using a Conductive ITO-PET Slide
- Bioorthogonal Chemistry in Neurobiology: From Imaging to Proteomics
- Inhibitory Mechanism of Bee Venom Against A431 Cutaneous Squamous Cell Carcinoma Cells Based on Label-Free Proteomics and Untargeted Metabolomics
- Nutritional modulation of microbiome proteomics in insulin resistance
BibTeX
@article{bielow2026wildac,
title = {{Wild-AC: A fast, index-free multi-pattern string matching algorithm with wildcard support for proteomics.}},
author = {Chris Bielow},
journal = {BMC bioinformatics},
year = {2026},
month = oct,
doi = {10.1186/s12859-026-06686-8},
url = {https://europepmc.org/article/MED/42864605},
note = {CC BY},
}
RIS
TY - JOUR
TI - Wild-AC: A fast, index-free multi-pattern string matching algorithm with wildcard support for proteomics.
AU - Chris Bielow
PY - 2026
DA - 2026/10/09
JO - BMC bioinformatics
DO - 10.1186/s12859-026-06686-8
UR - https://europepmc.org/article/MED/42864605
AB - Background Efficient multi-pattern string matching with wildcard support is essential in proteomics, where peptides must be mapped to protein databases containing ambiguous amino acids (e.g., B, Z, X). Existing approaches either require preprocessing (e.g., FM-index) or fail to handle wildcards in the text.Results We present Wild-AC, a modified Aho-Corasick algorithm that supports wildcards in the text by branching the search into parallel 'scout' paths, one per possible wildcard representation, while the unmodified primary search continues unaffected in the common, wildcard-free case. Wild-AC outperforms the FM-index (wildcard case) and matches or exceeds Wu-Manber (exact search) in speed for realistic proteomics workloads, i.e., 1000-500 000 peptide patterns (average length ∼18 amino acids) searched against protein databases (texts) of 3 × 10⁶-2.1 × 10⁸ characters. On databases masked to a wildcard rate of 5%, Wild-AC retains its advantage for large peptide sets, while the FM-index becomes preferable for small ones. It requires no index, scales well with pattern count, and supports multi-threading. The C++ implementation is open source at https://github.com/Wild-AC/Wild-AC .Conclusion Wild-AC extends the Aho-Corasick algorithm to support wildcards and outperforms FM-Index and Wu-Manber in the task of peptide-protein mapping while considering ambiguous amino acids.
SN - 1471-2105
ER -