FM Index

FM-index is an important component of Bowtie algorithm allowing it to obtain small memory footprint for the indices. In this commentary, we shall give you a list of important developments in computer science related to pattern searching so that you know the historical context of those discoveries. The presentation here will consist of a set of links and brief explanation of why the algorithm was a major improvement over the existing landscape. In the subsequent posts, we shall go into details of some of those algorithms related to NGS search.

Paolo Ferragina and Giovanni Manzini (2000). “Opportunistic Data Structures with Applications”. Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390. ^ Paolo Ferragina and Giovanni Manzini (2005). “Indexing Compressed Text”. Journal of the ACM (JACM), 52, 4 (Jul. 2005). p. 553