43 citations · 93 across the 20 of their papers we have counts for
19 papers · 1 filter
BWT for string collections
Davide Cenzato, Zsuzsanna Lipták, Nadia Pisanti +2
We survey the different methods used for extending the BWT to collections of strings, following largely [Cenzato and Lipták, CPM 2022, Bioinformatics 2024]. We analyze the specific…
Generalization of Repetitiveness Measures for Two-Dimensional Strings
Lorenzo Carfagna, Giovanni Manzini, Giuseppe Romana +2
The problem of detecting and measuring the repetitiveness of one-dimensional strings has been extensively studied in data compression and text indexing. Our understanding of these…
Faster run-length compressed suffix arrays
Nathaniel K. Brown, Travis Gagie, Giovanni Manzini +2
We first review how we can store a run-length compressed suffix array (RLCSA) for a text of length over an alphabet of size whose Burrows-Wheeler Transform (BWT) consis…
Exploring Repetitiveness Measures for Two-Dimensional Strings
Giuseppe Romana, Marinella Sciortino, Cristian Urbina
Detecting and measuring repetitiveness of strings is a problem that has been extensively studied in data compression and text indexing. However, when the data are structured in a n…
Bit catastrophes for the Burrows-Wheeler Transform
Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták +3
A bit catastrophe, loosely defined, is when a change in just one character of a string causes a significant change in the size of the compressed string. We study this phenomenon fo…
Computing matching statistics on Wheeler DFAs
Alessio Conte, Nicola Cotumaccio, Travis Gagie +3
Matching statistics were introduced to solve the approximate string matching problem, which is a recurrent subroutine in bioinformatics applications. In 2010, Ohlebusch et al. [SPI…
Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform
Travis Gagie, Giovanni Manzini, Marinella Sciortino
The Burrows-Wheeler Transform (BWT) is often taught in undergraduate courses on algorithmic bioinformatics, because it underlies the FM-index and thus important tools such as Bowti…
A New Class of String Transformations for Compressed Text Indexing
Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo +2
Introduced about thirty years ago in the field of Data Compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance…
Computing the original eBWT faster, simpler, and with less memory
Christina Boucher, Davide Cenzato, Zsuzsanna Lipták +2
Mantaci et al. [TCS 2007] defined the eBWT to extend the definition of the BWT to a collection of strings, however, since this introduction, it has been used more generally to desc…
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták +3
The Burrows-Wheeler-Transform (BWT), a reversible string transformation, is one of the fundamental components of many current data structures in string processing. It is central in…
String Attractors and Combinatorics on Words
Sabrina Mantaci, Antonio Restivo, Giuseppe Romana +2
The notion of \emph{string attractor} has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-ba…
The Alternating BWT: an algorithmic perspective
Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo +2
The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures,…
Inducing the Lyndon Array
Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini +2
In this paper we propose a variant of the induced suffix sorting algorithm by Nong (TOIS, 2013) that computes simultaneously the Lyndon array and the suffix array of a text in $O(n…
A New Class of Searchable and Provably Highly Compressible String Transformations
Raffaele Giancarlo, Giovanni Manzini, Giovanna Rosone +1
The Burrows-Wheeler Transform is a string transformation that plays a fundamental role for the design of self-indexing compressed data structures. Over the years, researchers have…
The colored longest common prefix array computed via sequential scans
F. Garofalo, G. Rosone, M. Sciortino +1
Due to the increased availability of large datasets of biological sequences, the tools for sequence comparison are now relying on efficient alignment-free approaches to a greater e…
Detecting Mutations by eBWT
Nicola Prezza, Nadia Pisanti, Marinella Sciortino +1
In this paper we develop a theory describing how the extended Burrows-Wheeler Transform (eBWT) of a collection of DNA fragments tends to cluster together the copies of nucleotides…
Lightweight LCP Construction for Very Large Collections of Strings
Anthony J. Cox, Fabio Garofalo, Giovanna Rosone +1
The longest common prefix array is a very advantageous data structure that, combined with the suffix array and the Burrows-Wheeler transform, allows to efficiently compute some com…
Sorting suffixes of a text via its Lyndon Factorization
Sabrina Mantaci, Antonio Restivo, Giovanna Rosone +1
The process of sorting the suffixes of a text plays a fundamental role in Text Algorithms. They are used for instance in the constructions of the Burrows-Wheeler transform and the…
Lightweight LCP Construction for Next-Generation Sequencing Datasets
Markus J. Bauer, Anthony J. Cox, Giovanna Rosone +1
The advent of "next-generation" DNA sequencing (NGS) technologies has meant that collections of hundreds of millions of DNA sequences are now commonplace in bioinformatics. Knowing…