Back to papers

On the String Matching with k Differences in DNA Databases

Summary: Proposes a BWT(y) index for approximate string matching with up to k edits in large DNA databases, enabling efficient querying of short patterns in massive genomes. Decomposes x into l subpatterns, uses BWT(y) to locate candidates within floor(k/l) differences, then rechecks; time O(k|T|) with |T| ≈ O(|Σ| 2^k), scalable for k ≤ log_{|Σ|} n; experiments show promise. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID

12605

Venue

VLDB

Year

2021

Pagerank

-

Overall Rank

13,272 | 7.67%

DOI

10.14778/3447689.3447695