SAIS-OPT: On the characterization and optimization of the SA-IS algorithm for suffix array construction

The suffix array and Burrows-Wheeler Transform are critical index structures in next generation sequence analysis. The construction of such index structures for mammalian-sized genomes can take thousands of seconds (i.e. tens of minutes). Its construction is complicated by computational overheads that coming from irregular or complex memory-access patterns. This paper rigorously characterizes the execution profile of the SA-IS algorithm in order to guide its optimization. The resulting optimized SA-IS, which we refer to as sais-opt, outperforms previous implementations of SA-IS as well as “best in practice” algorithms, when applied to large DNA strings.