A survey of BWT variants for string collections
D Cenzato, Z Lipták - Bioinformatics, 2024 - academic.oup.com
Motivation In recent years, the focus of bioinformatics research has moved from individual
sequences to collections of sequences. Given the fundamental role of the Burrows-Wheeler …
sequences to collections of sequences. Given the fundamental role of the Burrows-Wheeler …
A survey of BWT variants for string collections
D Cenzato, Z Lipták - arXiv preprint arXiv:2202.13235, 2022 - arxiv.org
In recent years, the focus of bioinformatics research has moved from individual sequences to
collections of sequences. Given the fundamental role of the Burrows-Wheeler Transform …
collections of sequences. Given the fundamental role of the Burrows-Wheeler Transform …
[HTML][HTML] Efficient construction of the BWT for repetitive text using string compression
D Díaz-Domínguez, G Navarro - Information and Computation, 2023 - Elsevier
We present a new semi-external algorithm that builds the Burrows–Wheeler transform
variant of Bauer et al.(aka, BCR BWT) in linear expected time. Our method uses …
variant of Bauer et al.(aka, BCR BWT) in linear expected time. Our method uses …
Computing the optimal BWT of very large string collections
D Cenzato, V Guerrini, Z Lipták… - 2023 Data Compression …, 2023 - ieeexplore.ieee.org
It is known that the exact form of the Burrows-Wheeler Transform (BWT) of a string collection
depends, in most implementations, on the input order of the strings in the collection …
depends, in most implementations, on the input order of the strings in the collection …
[HTML][HTML] r-indexing the eBWT
Abstract The extended Burrows-Wheeler Transform (eBWT) was introduced by Mantaci et
al.[TCS 2007] to extend the definition of the BWT to a collection of strings. As opposed to …
al.[TCS 2007] to extend the definition of the BWT to a collection of strings. As opposed to …
Building a pangenome alignment index via recursive prefix-free parsing
Pangenomics alignment offers a solution to reduce bias in biomedical research.
Traditionally, short-read aligners like Bowtie and BWA indexed a single reference genome …
Traditionally, short-read aligners like Bowtie and BWA indexed a single reference genome …
phyBWT2: phylogeny reconstruction via eBWT positional clustering
Background Molecular phylogenetics studies the evolutionary relationships among the
individuals of a population through their biological sequences. It may provide insights about …
individuals of a population through their biological sequences. It may provide insights about …
Generic Non-recursive Suffix Array Construction
J Olbrich, E Ohlebusch, T Büchler - ACM Transactions on Algorithms, 2024 - dl.acm.org
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 …
and consequently there is a multitude of suffix sorting algorithms. However, to this date the …
Bijective BWT based compression schemes
We investigate properties of the bijective Burrows-Wheeler transform (BBWT). We show that
for any string w, a bidirectional macro scheme of size O (r B) can be induced from the BBWT …
for any string w, a bidirectional macro scheme of size O (r B) can be induced from the BBWT …