2026-07-22T08:35:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23917 2026-02-09T06:23:56Z ddc:004 open_access

Search Schemes for Approximate Pattern Matching: An Overview Depuydt, Lore Fostier, Jan Gottlieb, Simon Kucherov, Gregory Reinert, Knut Renders, Luca FM-index bidirectional index approximate pattern matching search scheme We provide a brief survey of results on solving the approximate pattern matching problem using search schemes, as introduced by Kucherov et al. (2016). We demonstrate that search schemes constitute a flexible and versatile tool that enable the specification of various search strategies, including several known filtering methods. We present approaches for designing efficient search schemes and for implementing them effectively. Finally, we conclude with experimental results comparing multiple search schemes on DNA sequencing data using the Columba software by Renders et al. (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lore Depuydt and Jan Fostier and Simon Gottlieb and Gregory Kucherov and Knut Reinert and Luca Renders 2025 Is Part Of OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Manzini.9 urn:nbn:de:0030-drops-239172 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.9 eng https://creativecommons.org/licenses/by/4.0/legalcode