Lightweight algorithms for constructing and inverting the BWT of string collections
From MaRDI portal
Publication:390898
DOI10.1016/j.tcs.2012.02.002zbMath1292.68176OpenAlexW2051511420MaRDI QIDQ390898
Giovanna Rosone, Markus J. Bauer, Anthony J. Cox
Publication date: 9 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.002
Analysis of algorithms (68W40) Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)
Related Items
An external-memory algorithm for string graph construction, Lightweight LCP construction for very large collections of strings, Computing the original eBWT faster, simpler, and with less memory, Bidirectional Variable-Order de Bruijn Graphs, The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words, Wheeler graphs: a framework for BWT-based data structures, A new class of string transformations for compressed text indexing, Suffix array and Lyndon factorization of a text, Efficient construction of the BWT for repetitive text using string compression, Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads, Constructing and indexing the bijective and extended Burrows-Wheeler transform, Space-efficient construction of compressed suffix trees, Full-Text Indexes for High-Throughput Sequencing, Burrows-Wheeler transform and LCP array construction in constant space, Inducing enhanced suffix arrays for string collections, Computing the multi-string BWT and LCP array in external memory, Unnamed Item, Unnamed Item, Lightweight merging of compressed indices based on BWT variants, Wheeler languages, Space-efficient computation of the LCP array from the Burrows-Wheeler transform, Detecting Mutations by eBWT, Haplotype-aware graph indexes, SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET
Uses Software
Cites Work
- A space and time efficient algorithm for constructing compressed suffix arrays
- Fast BWT in small space by blockwise suffix sorting
- An extension of the Burrows-Wheeler transform
- A new combinatorial approach to sequence comparison
- Space efficient linear time construction of suffix arrays
- Lightweight BWT Construction for Very Large String Collections
- Linear work suffix array construction
- Indexing compressed text
- Linear-Time Construction of Suffix Arrays
- Lightweight Data Indexing and Compression in External Memory
- Linear Time Suffix Array Construction Using D-Critical Substrings
- Combinatorial Pattern Matching