Parallel suffix sorting

Publication Year:
2001
Usage 635
Downloads 404
Abstract Views 231
Repository URL:
https://surface.syr.edu/eecs/64
Author(s):
Futamura, Natsuhiko; Aluru, Srinivas; Kurtz, Stefan
Tags:
burrows-wheeler transform; computational biology; suffix arrays; suffix trees; Computer Sciences
article description
We present a parallel algorithm for lexicographically sorting the suffixes of a string. Suffix sorting has applications in string processing, data compression and computational biology. The ordered list of suffixes of a string stored in an array is known as Suffix Array, an important data structure in string processing and computational biology. Our focus is on deriving a practical implementation that works well for typical inputs rather than achieving the best possible asymptotic running-time for artificial, worst-case inputs. We experimentally evaluated our algorithm on an IBM SP-2 using genomes of several organisms. Our experiments show that the algorithm delivers good, scalable performance.