SeArcH schemes for Approximate stRing mAtching.

ABSTRACT: Finding approximate occurrences of a query in a text using a full-text index is a central problem in stringology with many applications, especially in bioinformatics. The recent work has shown significant speed-ups by combining bidirectional indices and employing variations of search schemes. Search schemes partition a query and describe how to search the resulting parts with a given error bound. The performance of search schemes can be approximated by the node count, which represents an upper bound of the number of search steps. Finding optimum search schemes is a difficult combinatorial optimization problem that becomes hard to solve for four and more errors. This paper improves on a few topics important to search scheme based searches: First, we show how search sche

SUBMITTER: Gottlieb SG 

PROVIDER: S-EPMC11915513 | biostudies-literature | 2025 Mar

REPOSITORIES: biostudies-literature