A survey of string orderings and their application to the Burrows-Wheeler transform

DOI10.1016/J.TCS.2017.02.021MaRDI QIDQ1698705zbMATH OpenOpenAlexFDO

Authors Jacqueline W. Daykin, Richard Groult, Yannick Guesnet, Thierry Lecroq, A. Lefebvre, M. Léonard, Élise Prieur-Gaston

Publication date 16 February 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2017.02.021

zbMATH Keywords

Lyndon wordalgorithmdegeneratelexicographic order\(V\)-ordersuffix arrayBurrows-Wheeler transformdata clustering\(B\)-wordbinary alphabetblock orderinverse transformsuffix-sortingbijective\(GB\)-word\(T\)-ordergeneric alphabetgeneric block orderindeterminate Lyndon word

Mathematics Subject Classification ID

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

Recommendations

• A bijective variant of the Burrows-Wheeler transform using \(V\)-order
• Binary block order Rouen transform
• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index
• Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
• Block sorting-based transformations on words: beyond the magic BWT

Cites work

• scientific article; zbMATH DE number 1146223 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• A bijective variant of the Burrows-Wheeler transform using \(V\)-order
• A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
• A four-stage algorithm for updating a Burrows-Wheeler transform
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
• A note on the Burrows-Wheeler transformation
• Binary block order Rouen transform
• Combinatorial Pattern Matching
• Computing the Burrows-Wheeler transform in place and in small space
• Data compression. The complete reference.
• Factorizing words over an ordered alphabet
• Free differential calculus. IV: The quotient groups of the lower central series
• Lightweight LCP Construction for Next-Generation Sequencing Datasets
• Lightweight LCP construction for very large collections of strings
• Linear Time Suffix Array Construction Using D-Critical Substrings
• Linear work suffix array construction
• Lyndon-like and V-order factorizations of strings
• On Burnside's Problem
• Ordering Integer Vectors for Coordinate Deletions
• Simple linear comparison of strings in \(V\)-order
• Space efficient linear time construction of suffix arrays
• String comparison and Lyndon-like factorization using V-order in linear time
• Suffix array and Lyndon factorization of a text
• \(V\)-order: new combinatorial properties \& a simple comparison algorithm

Cited in

(11)

• Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
• On the number of equal-letter runs of the bijective Burrows-Wheeler transform
• On the possible patterns of inputs for block sorting in the Burrows-Wheeler transformation
• When a dollar makes a BWT
• Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform \& the FM-index
• Suffixes, conjugates and Lyndon words
• A bijective variant of the Burrows-Wheeler transform using \(V\)-order
• Binary block order Rouen transform
• Sorting conjugates and suffixes of words in a multiset
• Computing the Burrows-Wheeler Transform of a String and Its Reverse
• Computing Burrows-Wheeler similarity distributions for string collections

Describes a project that uses

Uses Software

• Soap
• BWA

This page was built for publication: A survey of string orderings and their application to the Burrows-Wheeler transform

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