other · Universität Ulm, Kommunikations- und Informationszentrum (kiz) · 2024

Generic non-recursive suffix array construction

Olbrich, Jannik, Ohlebusch, Enno, Büchler, Thomas

Cited by 0Open access

Abstract

The suffix array is arguably one of the most important data structures in sequence analysis and consequently there is a multitude of suffix sorting algorithms. However, to this date the GSACA algorithm introduced in 2015 is the only known non-recursive linear-time suffix array construction algorithm (SACA). Despite its interesting theoretical properties, there has been little effort in improving GSACA’s non-competitive real-world performance. There is a super-linear algorithm DSH, which relies on the same sorting principle and is faster than DivSufSort, the fastest SACA for over a decade. The purpose of this article is twofold: We analyse the sorting principle used in GSACA and DSH and exploit its properties to give an optimised linear-time algorithm, and we show that it can be very elegantly used to compute both the original extended Burrows-Wheeler transform (eBWT) and a bijective version of the Burrows-Wheeler transform (BBWT) in linear time. We call the algorithm “generic,” since it can be used to compute the regular suffix array and the variants used for the BBWT and eBWT. Our suffix array construction algorithm is not only significantly faster than GSACA but also outperforms DivSufSort and DSH. Our BBWT-algorithm is faster than or competitive with all other tested BBWT construction implementations on large or repetitive data, and our eBWT-algorithm is faster than all other programs on data that is not extremely repetitive.

Cite this paper

APA 7

Olbrich, J., Ohlebusch, E., & Büchler, T. (2024). Generic non-recursive suffix array construction. Universität Ulm, Kommunikations- und Informationszentrum (kiz). https://doi.org/10.18725/oparu-58685

MLA 9

Olbrich, Jannik, et al. “Generic non-recursive suffix array construction.” Universität Ulm, Kommunikations- und Informationszentrum (kiz), 2024, https://doi.org/10.18725/oparu-58685.

Chicago

Olbrich, Jannik, Enno Ohlebusch, and Thomas Büchler. 2024. “Generic non-recursive suffix array construction.” Universität Ulm, Kommunikations- und Informationszentrum (kiz). https://doi.org/10.18725/oparu-58685.

Harvard

Olbrich, J., Ohlebusch, E. and Büchler, T. (2024) ‘Generic non-recursive suffix array construction’, Universität Ulm, Kommunikations- und Informationszentrum (kiz). Available at: https://doi.org/10.18725/oparu-58685.

BibTeX

@misc{olbrich2024generic,
  title = {{Generic non-recursive suffix array construction}},
  author = {Olbrich, Jannik and Ohlebusch, Enno and Büchler, Thomas},
  journal = {Universität Ulm, Kommunikations- und Informationszentrum (kiz)},
  year = {2024},
  doi = {10.18725/oparu-58685}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.