{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T00:38:52Z","timestamp":1792543132563,"version":"4.5.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T00:00:00Z","timestamp":1791504000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,10,12]],"date-time":"2026-10-12T00:00:00Z","timestamp":1791763200000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>\n                      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.,\n                      <jats:italic>B<\/jats:italic>\n                      ,\n                      <jats:italic>Z<\/jats:italic>\n                      ,\n                      <jats:italic>X<\/jats:italic>\n                      ). Existing approaches either require preprocessing (e.g., FM-index) or fail to handle wildcards in the text.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>\n                      We present Wild-AC, a modified Aho-Corasick algorithm that supports wildcards in the text by branching the search into parallel \u2018scout\u2019 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\u2013500 000 peptide patterns (average length \u223c18 amino acids) searched against protein databases (texts) of 3 \u00d7 10\n                      <jats:sup>6<\/jats:sup>\n                      \u20132.1 \u00d7 10\n                      <jats:sup>8<\/jats:sup>\n                      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\n                      <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/Wild-AC\/Wild-AC\" ext-link-type=\"uri\">https:\/\/github.com\/Wild-AC\/Wild-AC<\/jats:ext-link>\n                      .\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>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.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-026-06686-8","type":"journal-article","created":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T14:43:39Z","timestamp":1791557019000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Wild-AC: A fast, index-free multi-pattern string matching algorithm with wildcard support for proteomics"],"prefix":"10.1186","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5756-3988","authenticated-orcid":false,"given":"Chris","family":"Bielow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,10,9]]},"reference":[{"key":"6686_CR1","doi-asserted-by":"publisher","unstructured":"Navarro G, Raffinot M. Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences. Cambridge University Press, May 2002. ISBN 9781316135228. https:\/\/doi.org\/10.1017\/cbo9781316135228.","DOI":"10.1017\/cbo9781316135228"},{"key":"6686_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho AV, Corasick MJ. Efficient string matching: an aid to bibliographic search. Commun ACM. 1975;18:333\u201340. https:\/\/doi.org\/10.1145\/360825.360855. JuneISSN 1557-7317","journal-title":"Commun ACM"},{"key":"6686_CR3","doi-asserted-by":"publisher","unstructured":"Ferragina P, Manzini G. Opportunistic data structures with applications. In Proceedings 41st Annual Symposium on Foundations of Computer Science, SFCS-00, pages 390\u2013398. IEEE Comput. Soc, 2000. https:\/\/doi.org\/10.1109\/sfcs.2000.892127.","DOI":"10.1109\/sfcs.2000.892127"},{"key":"6686_CR4","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R Baeza-Yates","year":"1992","unstructured":"Baeza-Yates R, Gonnet GH. A new approach to text searching. Commun ACM. 1992;35:74\u201382. https:\/\/doi.org\/10.1145\/135239.135243. OctoberISSN 1557-7317","journal-title":"Commun ACM"},{"key":"6686_CR5","unstructured":"Wu S, Manber U. A fast algorithm for multi-pattern searching. 1994. URL https:\/\/api.semanticscholar.org\/ CorpusID:15826173."},{"key":"6686_CR6","doi-asserted-by":"publisher","unstructured":"Commentz-Walter B. A string matching algorithm fast on the average: extended abstract, pages 118-32. Springer Berlin Heidelberg, 1979. ISBN 9783540351689. https:\/\/doi.org\/10.1007\/3-540-09510-1_10.","DOI":"10.1007\/3-540-09510-1_10"},{"key":"6686_CR7","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/351827.384246","volume":"5","author":"G Navarro","year":"2000","unstructured":"Navarro G, Raffinot M. Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM J Exp Algorithmics. 2000;5:4 https:\/\/doi.org\/10.1145\/351827.384246. DecemberISSN 1084-6654","journal-title":"ACM J Exp Algorithmics"},{"key":"6686_CR8","doi-asserted-by":"publisher","unstructured":"Padmashani R, Sathyadevan S, Dath D. Bsnort ips better snort intrusion detection \/ prevention system. In 2012 12th International Conference on Intelligent Systems Design and Applications (ISDA), pages 46\u201351. IEEE, November 2012. https:\/\/doi.org\/10.1109\/isda.2012.6416511.","DOI":"10.1109\/isda.2012.6416511"},{"key":"6686_CR9","doi-asserted-by":"publisher","first-page":"2702","DOI":"10.1093\/bioinformatics\/btw241","volume":"32","author":"BJ Woodcroft","year":"2016","unstructured":"Woodcroft BJ, Boyd JA, Tyson GW. Orfm: a fast open reading frame predictor for metagenomic data. Bioinformatics. 2016;32:2702\u20133. https:\/\/doi.org\/10.1093\/bioinformatics\/btw241. MayISSN 1367-4803","journal-title":"Bioinformatics"},{"key":"6686_CR10","doi-asserted-by":"publisher","unstructured":"Thambawita DRVLB, Ragel RG, Elkaduwe D. An optimized parallel failure-less aho-corasick algorithm for dna sequence matching. In 2016 IEEE International Conference on Information and Automation for Sustainability (ICIAfS), pages 1\u20136. IEEE, December 2016. https:\/\/doi.org\/10.1109\/iciafs.2016.7946533.","DOI":"10.1109\/iciafs.2016.7946533"},{"key":"6686_CR11","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/bf01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen E. On-line construction of suffix trees. Algorithmica. 1995;14:249\u201360. https:\/\/doi.org\/10.1007\/bf01206331. SeptemberISSN 1432-0541","journal-title":"Algorithmica"},{"key":"6686_CR12","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers G. Suffix arrays: A new method for on-line string searches. SIAM J Comput. 1993;22:935\u201348. https:\/\/doi.org\/10.1137\/0222058. OctoberISSN 1095-7111","journal-title":"SIAM J Comput"},{"key":"6686_CR13","doi-asserted-by":"publisher","unstructured":"Gagie T, Karhu K, K\u00e4rkk\u00e4inen J, M\u00e4kinen V, Salmela L, Tarhio J. Indexed multi-pattern matching, pages 399\u2013407. Springer Berlin Heidelberg, 2012. ISBN 9783642293443. https:\/\/doi.org\/10.1007\/978-3-642-29344-3_34.","DOI":"10.1007\/978-3-642-29344-3_34"},{"key":"6686_CR14","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jda.2013.03.007","volume":"24","author":"S Gog","year":"2014","unstructured":"Gog S, Karhu K, K\u00e4rkk\u00e4inen J, M\u00e4kinen V, V\u00e4lim\u00e4ki N. Multi-pattern matching with bidirectional indexes. J Discret Algorithms. 2014;24:26\u201339. https:\/\/doi.org\/10.1016\/j.jda.2013.03.007. JanuaryISSN 1570-8667","journal-title":"J Discret Algorithms"},{"key":"6686_CR15","doi-asserted-by":"publisher","unstructured":"Hauswedell H, Hetzel S, Gottlieb SG, Kretzmer H, Meissner A, Reinert K. Lambda3: homology search for protein, nucleotide, and bisulfite- converted sequences. Bioinformatics, 40, March 2024. ISSN 1367-4811. https:\/\/doi.org\/10.1093\/bioinformatics\/btae097.","DOI":"10.1093\/bioinformatics\/btae097"},{"key":"6686_CR16","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1038\/s41592-021-01101-x","volume":"18","author":"B Buchfink","year":"2021","unstructured":"Buchfink B, Reuter K, Drost H-G. Sensitive protein alignments at tree-of-life scale using diamond. Nat Methods. 2021;18:366\u20138. https:\/\/doi.org\/10.1038\/s41592-021-01101-x. AprilISSN 1548-7105","journal-title":"Nat Methods"},{"key":"6686_CR17","doi-asserted-by":"publisher","first-page":"1530","DOI":"10.1093\/bioinformatics\/btn223","volume":"24","author":"K Pr\u00fcfer","year":"2008","unstructured":"Pr\u00fcfer K, Stenzel U, Dannemann M, Green RE, Lachmann M, Kelso J. Patman: rapid alignment of short sequences to large databases. Bioinformatics. 2008;24:1530\u20131. https:\/\/doi.org\/10.1093\/bioinformatics\/btn223. JulyISSN 1367-4811","journal-title":"Bioinformatics"},{"key":"6686_CR18","doi-asserted-by":"publisher","first-page":"283","DOI":"10.3233\/IDA-205087","volume":"25","author":"N Liu","year":"2021","unstructured":"Liu N, Xie F, Wu X. Suffix array for multi- pattern matching with variable length wildcards. Intell Data Anal. 2021;25:283\u2013303. https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/IDA-205087","journal-title":"Intell Data Anal"},{"key":"6686_CR19","doi-asserted-by":"publisher","unstructured":"Renders L, Depuydt L, Rahmann S, Fostier J. Automated design of efficient search schemes for lossless approximate pattern matching, pages 164-84. Switzerland: Springer Nature, 2024. ISBN 9781071639894. https:\/\/doi.org\/10.1007\/978-1-0716-3989-4_11.","DOI":"10.1007\/978-1-0716-3989-4_11"},{"key":"6686_CR20","doi-asserted-by":"publisher","first-page":"2042","DOI":"10.1093\/bioinformatics\/btx122","volume":"33","author":"D Kopczynski","year":"2017","unstructured":"Kopczynski D, Barsnes H. P\u00e5l R. Nj\u00f8lstad, Albert Sickmann, Marc Vaudel, and Robert Ahrends. PeptideMapper: efficient and versatile amino acid sequence and tag mapping. Bioinformatics. 2017;33:2042\u20134. https:\/\/academic.oup.com\/bioinformatics\/article\/33\/13\/2042\/3059929 JulyISSN 1367-4803, 1367-4811. doi: 10.1093\/bioinformatics\/btx122. URL","journal-title":"Bioinformatics"},{"key":"6686_CR21","unstructured":"Gottlieb SG. FMIndex-collection. URL https:\/\/github.com\/SGSSGene\/fmindex-collection."},{"key":"6686_CR22","doi-asserted-by":"publisher","first-page":"lqaf025","DOI":"10.1093\/nargab\/lqaf025","volume":"7","author":"SG Gottlieb","year":"2025","unstructured":"Gottlieb SG, Reinert K. SeArcH schemes for approximate stRing mAtching. NAR Genomics Bioinforma. 2025;7:lqaf025 https:\/\/academic.oup.com\/nargab\/article\/doi\/10.1093\/nargab\/lqaf025\/8084725","journal-title":"NAR Genomics Bioinforma"},{"key":"6686_CR23","doi-asserted-by":"publisher","first-page":"4337","DOI":"10.1021\/acs.jproteome.8b00544","volume":"17","author":"L Mendoza","year":"2018","unstructured":"Mendoza L, Deutsch EW, Sun Z, Campbell DS, Shteynberg DD, Moritz RL. Flexible and fast mapping of peptides to a proteome with proteomapper. J Proteome Res. 2018;17:4337\u201344. https:\/\/pubs.acs.org\/doi\/10.1021\/acs.jproteome.8b00544","journal-title":"J Proteome Res"},{"key":"6686_CR24","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10115-015-0873-0","volume":"48","author":"S Kanda","year":"2015","unstructured":"Kanda S, Fuketa M, Morita K, Aoe J. A compression method of double-array structures using linear functions. Knowl Inf Syst. 2015;48:55\u201380. https:\/\/doi.org\/10.1007\/s10115-015-0873-0. AugustISSN 0219-3116","journal-title":"Knowl Inf Syst"},{"key":"6686_CR25","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1038\/s41592-024-02197-7","volume":"21","author":"J Pfeuffer","year":"2024","unstructured":"Pfeuffer J, Bielow C, Wein S, Jeong K, Netz E, Walter A, et al. OpenMS 3 enables reproducible analysis of large-scale mass spectrometry data. Nat Methods. 2024;21:365\u20137. https:\/\/www.nature.com\/articles\/s41592-024-02197-7","journal-title":"Nat Methods"},{"key":"6686_CR26","doi-asserted-by":"publisher","first-page":"D609","DOI":"10.1093\/nar\/gkae1010","volume":"53","author":"A Bateman","year":"2024","unstructured":"Bateman A, Martin M-J, Orchard S, Magrane M, Adesina A, Ahmad S, et al. Uniprot: the universal protein knowledgebase in 2025. Nucleic Acids Res. 2024;53:D609\u2013D617. https:\/\/doi.org\/10.1093\/nar\/gkae1010. NovemberISSN 1362-4962","journal-title":"Nucleic Acids Res"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-026-06686-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-026-06686-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-026-06686-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T00:05:24Z","timestamp":1792541124000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-026-06686-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,9]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["6686"],"URL":"https:\/\/doi.org\/10.1186\/s12859-026-06686-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-9609256\/v1","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,9]]},"assertion":[{"value":"4 May 2026","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable","order":1,"name":"Ethics","label":"Ethics approval and consent to participate","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable","order":2,"name":"Ethics","label":"Consent for publication","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"CB is a post-doctoral researcher with a focus on efficient algorithms and quality control in proteomics. He currently leads the Proteomics Section at the Bioinformatics Solutions Center, Freie Universit\u00e4t Berlin.","order":3,"name":"Ethics","label":"Authors\u2019 information","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":4,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"234"}}