Rxivist logo

Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index

By Kiavash Kianfar, Christopher Pockrandt, Bahman Torkamandi, Haochen Luo, Knut Reinert

Posted 13 Apr 2018
bioRxiv DOI: 10.1101/301085

Finding approximate occurrences of a pattern in a text using a full-text index is a central problem in bioinformatics and has been extensively researched. Bidirectional indices have opened new possibilities in this regard allowing the search to start from anywhere within the pattern and extend in both directions. In particular, use of search schemes (partitioning the pattern and searching the pieces in certain orders with given bounds on errors) can yield significant speed-ups. However, finding optimal search schemes is a difficult combinatorial optimization problem. Here for the first time, we propose a mixed integer program (MIP) capable to solve this optimization problem for Hamming distance with given number of pieces. Our experiments show that the optimal search schemes found by our MIP significantly improve the performance of search in bidirectional FM-index upon previous ad-hoc solutions. For example, approximate matching of 101-bp Illumina reads (with two errors) becomes 35 times faster than standard backtracking. Moreover, despite being performed purely in the index, the running time of search using our optimal schemes (for up to two errors) is comparable to the best state-of-the-art aligners, which benefit from combining search in index with in-text verification using dynamic programming. As a result, we anticipate a full-fledged aligner that employs an intelligent combination of search in the bidirectional FM-index using our optimal search schemes and in-text verification using dynamic programming outperforms today's best aligners. The development of such an aligner, called FAMOUS (Fast Approximate string Matching using OptimUm search Schemes), is ongoing as our future work.

Download data

  • Downloaded 457 times
  • Download rankings, all-time:
    • Site-wide: 41,890 out of 103,764
    • In bioinformatics: 5,059 out of 9,474
  • Year to date:
    • Site-wide: 75,352 out of 103,764
  • Since beginning of last month:
    • Site-wide: 64,262 out of 103,764

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)