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.