Computing the Burrows-Wheeler transform of a string and its reverse in parallel

DOI10.1016/J.JDA.2013.06.002MaRDI QIDQ2442813zbMATH OpenOpenAlexFDO

Authors Enno Ohlebusch, Timo Beller, Mohamed Ibrahim Abouelhoda

Publication date 1 April 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2013.06.002

zbMATH Keywords

Burrows-Wheeler transformparallel computingreverse stringwavelet tree

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Recommendations

• Computing the Burrows-Wheeler Transform of a String and Its Reverse
• Parallel computation of the Burrows Wheeler transform in compact space
• Parallel algorithms for Burrows-Wheeler compression and decompression
• Bit-parallel approximate string matching algorithms with transposition
• scientific article; zbMATH DE number 975424
• Burrows-Wheeler transform and run-length enconding
• Computing the Burrows-Wheeler transform in place and in small space
• Computing the parameterized Burrows-Wheeler transform online
• FUNCTIONAL PEARL Inverting the Burrows–Wheeler transform
• scientific article; zbMATH DE number 1421005

Cites work

• Algorithm Theory - SWAT 2004
• Algorithms on Strings, Trees and Sequences
• Approximate All-Pairs Suffix/Prefix Overlaps
• Bidirectional search in a string with wavelet trees
• Compressed suffix trees, efficient computation and storage of LCP-values
• Computing the Burrows-Wheeler Transform of a String and Its Reverse
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Permuted Longest-Common-Prefix Array
• Top-\(k\) ranked document search in general text databases

Cited in

(8)

• Parallel processing of encoded bit strings
• \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Parallel algorithms for Burrows-Wheeler compression and decompression
• Computing the Burrows-Wheeler Transform of a String and Its Reverse
• FUNCTIONAL PEARL Inverting the Burrows–Wheeler transform
• Tighter bounds for the sum of irreducible LCP values
• Computing Burrows-Wheeler similarity distributions for string collections

Describes a project that uses

Uses Software

• mkESA
• BWA

This page was built for publication: Computing the Burrows-Wheeler transform of a string and its reverse in parallel

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