Comparative Analysis of Algorithms for Implementing the FM-Index: Correctness, Complexity, and Use Cases

Question

[qwertyuiop26]

Analyze at least two algorithms you found for solving the problem of FM-index What are two algorithms that can be used to implement an FM-index for efficient text searching, and how do they differ in terms of correctness, complexity, and application use cases?" Which applications are most suited for each algorithm, and what are their specific strengths in those scenarios?" "Between these two algorithms, which trades computation for space, and which prioritizes efficiency at the expense of other resources?" "Which of these algorithms is easier to understand and implement for a beginner?

[Michael]

So this is your exam question or assignment? Please understand that posting this here is not doing anyone any good. You are supposed to learn something by spending time studying this for yourself. Other people (not to mention your supervisor) may consider copy-pasting assignments rude or unfair and will be put off helping you. If you want help from us, study your course materials and some relevant papers, if you still need help, come back with a concrete question about an algorithm or application.

[qwertyuiop26]

I'm sorry for any confusion or inconvenience. I'm seeking guidance on which search algorithms are used in the FM-index. I've done extensive research but couldn't identify a clear way to implement them, and I thought this platform could help me.

[Michael]

Why does your question sound like an assignment (if it's not, reformulate it, note you are in no position to give the volunteers here assignments)?

I've done extensive research but couldn't identify a clear way to implement them, and I thought this platform could help me.

Please provide some concrete evidence and background on which algorithms in particular you have investigated.

[qwertyuiop26]

I've implemented fm index with backward search and need an inexact search to implement on FM index, I couldn't understand how fm index could be implemented with an inexact search

Answer 1

[Michael]

So I am assuming you have calculated a Burrows-Wheeler transform, then add the FM-index for the first and last column of the BW-matrix. I recommend to have a look at Ben Langmead's lectures here:

• https://www.langmead-lab.org/teaching.html
• https://www.youtube.com/playlist?list=PL2mpR0RYFQsADmYpW2YWBrXJZ_6EL_3nu

He has some instructive code examples in Python too.

I do not quite understand your question on inexact search. In my understanding, BWT+FM-index as originally described is for fast retrieval of all exact occurrences of a string in a text. When this is used for matching strings with mismatches e.g. in sequencing reads, the BWT search can be used in a seed-extend pattern to first find shorter exact substrings of the search string, then extend them by dynamic programming.

https://www.cs.jhu.edu/~langmea/resources/lecture_notes/15_index_assisted_v2.pdf

There are algorithms undertaking approximate matching based on BWT directly, which means solving the k-mismatch problem. However, I am not sure how popular those are or if there are implementations.

Yangjun Chen, Yujia Wu, On the string matching with k mismatches, Theoretical Computer Science, Volume 726, 2018, Pages 5-29, ISSN 0304-3975, https://doi.org/10.1016/j.tcs.2018.02.001.