SeArcH schemes for Approximate stRing mAtching

Area of Science:

• Computational Biology
• Bioinformatics
• Stringology

Background:

• Approximate string matching with full-text indices is crucial for bioinformatics.
• Existing search schemes offer speed-ups but finding optimal schemes for multiple errors is challenging.

Purpose of the Study:

• To unify and extend existing approximate search strategies within the search scheme framework.
• To develop an improved heuristic for constructing search schemes, especially for higher error counts.
• To propose a more accurate performance metric for search algorithms.

Main Methods:

• Modeling existing approximate search strategies (suffix filters, 01*0-seeds, pigeonhole principle) as search schemes.
• Developing a novel heuristic for constructing search schemes applicable to any number of errors.
• Introducing and evaluating the 'weighted node count' as a performance metric.

Main Results:

• Unified diverse search strategies under the search scheme framework, enabling new schemes for any error count.
• Developed a heuristic search scheme construction that matches optimal schemes and improves node count for >= 4 errors.
• Demonstrated the limitations of node count and validated the accuracy of the weighted node count metric.

Conclusions:

• Search schemes provide a unified framework for approximate string matching.
• The new heuristic offers efficient search scheme construction for complex error scenarios.
• The weighted node count metric offers a more realistic performance evaluation for search algorithms.