gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections

The construction of a suffix array for a collection of strings is a fundamental task in Bioinformatics and in many other applications that process strings. Related data structures, as the Longest Common Prefix array, the Burrows-Wheeler transform, and the document array, are often needed to accompan...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms for molecular biology 2020-09, Vol.15 (1), p.18-18, Article 18
Main Authors: Louza, Felipe A, Telles, Guilherme P, Gog, Simon, Prezza, Nicola, Rosone, Giovanna
Format: Article
Language:English
Subjects:
Algorithms
Arrays
Bioinformatics
Burrows-Wheeler transform
Collection
Data structures
Deoxyribonucleic acid
DNA
Document array
LCP array
Light
Open source software
Proteins
Software
String collections
Strings
Suffix array
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The construction of a suffix array for a collection of strings is a fundamental task in Bioinformatics and in many other applications that process strings. Related data structures, as the Longest Common Prefix array, the Burrows-Wheeler transform, and the document array, are often needed to accompany the suffix array to efficiently solve a wide variety of problems. While several algorithms have been proposed to construct the suffix array for a single string, less emphasis has been put on algorithms to construct suffix arrays for string collections. In this paper we introduce gsufsort, an open source software for constructing the suffix array and related data indexing structures for a string collection with symbols in ( ) time. Our tool is written in ANSI/C and is based on the algorithm gSACA-K (Louza et al. in Theor Comput Sci 678:22-39, 2017), the fastest algorithm to construct suffix arrays for string collections. The tool supports large fasta, fastq and text files with multiple strings as input. Experiments have shown very good performance on different types of strings. gsufsort is a fast, portable, and lightweight tool for constructing the suffix array and additional data structures for string collections.
ISSN:1748-7188
1748-7188
DOI:10.1186/s13015-020-00177-y