Simple In-Place Suffix Array Construction by Walking along Burrows-Wheeler Transforms

Abstract. We present a family of simple algorithms that construct a representation of the suffix array of a text t by walking along the Burrows-Wheeler transforms (BWTs) of increasingly longer suffixes of t. One variant, called Walk-bothLR, builds the suffix array, its inverse, the BWT, and the longest common prefix array in linear time in practice (quadratic in the worst case), requiring only constant working space, and only consecutive left-to-right read/write access to secondary storage. Another variant, called Walk-minLR, is twice as fast as Walk-bothLR on random texts, and has worst-case time complexity O(n logn) for a text of length n. It needs one additional integer array as working space. While asymptotically faster algorithms exist, and compressed suffix ar-rays require even less memory, the algorithms presented here provide a good compromise between running time and memory requirements. They are especially well suited to build suffix arrays of large genomes, especially for long repeats. The O(n logn) time bound for Walk-minLR sheds a new light on the structure of BWTs. The algorithms are simple and easy to implement; software is freely available a