I noticed that FM-indexing is a preferred way to match strings in large data sets, and in particular DNA sequencing wiki-article. I know that with this method, it can eliminate space dependencies thanks to compression methods. However, alternatives like Knuth-Morris-Pratt Algorithm or Rabin-karp are highly effective in terms of extra space complexity with $O(|Pattern| + 1)$ and $O(1)$ respectively. These, are the complexity that would take if I were to code them so there might be better ways.

Overall, Burrows-Wheeler transform doesn't do all that much both in terms of time and space. So why is it favored? My current assumption is that it can be modified to do approximate pattern matching. Does that imply Rabin-karp or KMP cannot be modified to efficiently calculate approximate matches?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.