2026-08-27T21:20:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27525 2026-08-27T06:04:07Z ddc:004 open_access

Designing Exact Spaced Seed Filters Based on Combined Hit and Coverage Information Karami, Moein Zentgraf, Jens Rahmann, Sven Spaced seed Gapped k-mer Hit Coverage Integer linear program (ILP) Dynamic programming (DP) Similarity search We revisit the classical problem of designing exact gapped k-mer based filtration methods to find all occurrences of a given query sequence (e.g., DNA read) in a text (genome) with at most a given number of substitutions. Whereas many existing filtration methods use small k and initiate a computationally expensive further investigation on a single k-mer hit to guarantee no false negatives, we derive stricter filtration criteria based on both the number of k-mer hits and hit-covered positions. Notably, our criteria go beyond a simple logical AND of hit-based and coverage-based criteria. We provide methods based on both integer linear programs and dynamic programming to define optimal exact filter thresholds and compare the behavior of running times of both approaches. We then investigate to what degree a filter based on specific combinations of hits and coverage has better filtration efficiency than filters based on a single criterion (hits or coverage), or on a simple logical AND of both. We define two new quantities to characterize the filtration efficiency curve of a spaced seed for a specific sequence length and a desired tolerated number of changes. In a case study, we compare all symmetric masks with 25 significant positions in a window of 35 positions across four filtration criteria. Code is available at https://gitlab.com/rahmannlab/seed-optimization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moein Karami and Jens Zentgraf and Sven Rahmann 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.21 urn:nbn:de:0030-drops-275252 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.21 eng https://creativecommons.org/licenses/by/4.0/legalcode