Lossless Approximate Pattern Matching: Automated Design of Efficient Search Schemes

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithm Design

Background:

• Approximate pattern matching is crucial for sequence analysis, but designing efficient search schemes for higher error tolerances (k > 4) is computationally intensive.
• Existing methods struggle with scalability and efficiency when handling increased error rates in pattern matching.

Purpose of the Study:

• To develop an automated and efficient method for generating search schemes for lossless approximate pattern matching up to k=7 errors.
• To introduce a novel software tool, Columba, that implements these advanced search schemes for high-performance read mapping.

Main Methods:

• Integration of a greedy algorithm and a novel Integer Linear Programming (ILP) formulation for automated search scheme design.
• Development of Hato, an open-source tool for generating search schemes, and Columba 1.2, an open-source lossless read-mapper.
• Dynamic scheme selection technique to further optimize efficiency based on specific search patterns.

Main Results:

• Achieved efficient search schemes for up to k=7 errors, outperforming existing strategies in theoretical and practical analyses.
• Columba 1.2 demonstrates superior performance, mapping 100,000 Illumina reads (150 bp) with k=6 in 75 seconds and k=7 in 2.25 hours.
• Runtime reductions of up to 53% for higher k values and a four-fold higher mapping rate compared to a lossy tool.

Conclusions:

• The proposed ILP-based approach and dynamic scheme selection significantly enhance the efficiency of approximate pattern matching.
• Columba 1.2 represents a state-of-the-art lossless read-mapper, offering unprecedented speed and accuracy for high-throughput sequencing data analysis.