License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2022.20
URN: urn:nbn:de:0030-drops-170545
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17054/
Go to the corresponding LIPIcs Volume Portal

Lipták, Zsuzsanna ; Masillo, Francesco ; Puglisi, Simon J.

Suffix Sorting via Matching Statistics

pdf-format:
LIPIcs-WABI-2022-20.pdf (1.0 MB)

Abstract

We introduce a new algorithm for constructing the generalized suffix array of a collection of highly similar strings. As a first step, we construct a compressed representation of the matching statistics of the collection with respect to a reference string. We then use this data structure to distribute suffixes into a partial order, and subsequently to speed up suffix comparisons to complete the generalized suffix array. Our experimental evidence with a prototype implementation (a tool we call sacamats) shows that on string collections with highly similar strings we can construct the suffix array in time competitive with or faster than the fastest available methods. Along the way, we describe a heuristic for fast computation of the matching statistics of two strings, which may be of independent interest.

BibTeX - Entry

@InProceedings{liptak_et_al:LIPIcs.WABI.2022.20,
  author =	{Lipt\'{a}k, Zsuzsanna and Masillo, Francesco and Puglisi, Simon J.},
  title =	{{Suffix Sorting via Matching Statistics}},
  booktitle =	{22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-243-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{242},
  editor =	{Boucher, Christina and Rahmann, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17054},
  URN =		{urn:nbn:de:0030-drops-170545},
  doi =		{10.4230/LIPIcs.WABI.2022.20},
  annote =	{Keywords: Generalized suffix array, matching statistics, string collections, compressed representation, data structures, efficient algorithms}
}

Keywords: Generalized suffix array, matching statistics, string collections, compressed representation, data structures, efficient algorithms
Collection: 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)
Issue Date: 2022
Date of publication: 26.08.2022
Supplementary Material: Software (Source Code): https://github.com/fmasillo/sacamats

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI