Computing the original eBWT faster, simpler, and with less memory

DOI10.1007/978-3-030-86692-1_11MaRDI QIDQ2146134zbMATH OpenOpenAlexFDO

Authors Christina Boucher, Davide Cenzato, Zsuzsanna Lipták, Massimiliano Rossi, M. Sciortino

Publication date 15 June 2022

Full work available at URL https://arxiv.org/abs/2106.11191

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Cites work

• An extension of the Burrows-Wheeler transform
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Burrows-Wheeler transform and Sturmian words
• Computing the multi-string BWT and LCP array in external memory
• Construction of Fundamental Data Structures for Strings
• Counting permutations with given cycle structure and descent set
• Efficient algorithm for circular Burrows-Wheeler transform
• Efficient construction of a complete index for pan-genomics read alignment
• Fast canonization of circular strings
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• scientific article; zbMATH DE number 7695993 (Why is no real title available?)
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Lightweight metagenomic classification via eBWT
• On the combinatorics of suffix arrays
• PFP Compressed Suffix Trees
• Space efficient linear time construction of suffix arrays
• Suffix Arrays: A New Method for On-Line String Searches
• The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Words

Cited in

(13)

• r-indexing the eBWT
• A new class of string transformations for compressed text indexing
• Efficient construction of the BWT for repetitive text using string compression
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• r-indexing the eBWT
• A textbook solution for dynamic strings
• Sorting circular suffixes in linear time
• Bit catastrophes for the Burrows-Wheeler transform
• Generic non-recursive suffix array construction
• Simple linear time algorithm for sorting strings in omega-order with applications
• A textbook solution for dynamic strings
• Improved circular dictionary matching
• Fast and memory-efficient bwt construction of repetitive texts using Lyndon grammars

Describes a project that uses

Uses Software

• Big-BWT
• r-index

This page was built for publication: Computing the original eBWT faster, simpler, and with less memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2146134)