In short, my question is:
1. what is the running time of building FM-Index, is it linear in the sense of reference genome?

I was told that FM-Index can be built in linear time, i.e. O(n), where n is the length of reference genome.
But I actually can not find the paper describing it.

The paper cited mostly "Indexing Compressed Text" by Ferragina et al. 2004 focus on the analysis of memory footprint and query time analysis, but not the running time of building FM Index.


In 2003, two (or maybe three) conference papers first showed that suffix array can be constructed in linear time. As generating BWT from suffix array takes linear time, they also proved that FM-index can be constructed in linear time. One of the most influential linear-time algorithms, SA-IS, was invented by Nong et al (2008). They provided a ~100-line implementation in C. It is much simpler and faster than the previous works. Yuta Mori optimized Nong et al's implementation into the sais library. A few years ago (when I was still following the literature), that library was fastest linear-time implementation in practical benchmarks. However, at least at that time, libdivsufsort, an O(nlogn) algorithm developed also by Yuta Mori, was widely believed to be the fastest open-source library to construct suffix arrays, faster than sais. Linear-time algorithms are not necessarily faster. If a linear algorithm is associated with a large constant and lots of cache misses, an O(nlogn) algorithm can be faster in practice, just as Rob said.