Lightweight BWT construction for very large string collections

DOI10.1007/978-3-642-21458-5_20MaRDI QIDQ3011856zbMATH OpenOpenAlexFDO

Authors Markus J. Bauer, Anthony J. Cox, Giovanna Rosone

Publication date 29 June 2011

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21458-5_20

zbMATH Keywords

BWTnext-generation sequencingtext indexes

Mathematics Subject Classification ID

Algorithms on strings (68W32) Protein sequences, DNA sequences (92D20)

Recommendations

• Lightweight algorithms for constructing and inverting the BWT of string collections
• Lightweight data indexing and compression in external memory
• Lightweight LCP construction for very large collections of strings
• Computing the multi-string BWT and LCP array in external memory
• Divide and conquer computation of the multi-string BWT and LCP array

Cites work

• A new combinatorial approach to sequence comparison
• A space and time efficient algorithm for constructing compressed suffix arrays
• An extension of the Burrows-Wheeler transform
• Combinatorial Pattern Matching
• Indexing compressed text
• Lightweight data indexing and compression in external memory
• Linear Time Suffix Array Construction Using D-Critical Substrings
• Linear work suffix array construction
• Linear-time construction of suffix arrays (extended abstract)
• Space efficient linear time construction of suffix arrays

Cited in

(10)

• Divide and conquer computation of the multi-string BWT and LCP array
• Computing the multi-string BWT and LCP array in external memory
• Lightweight merging of compressed indices based on BWT variants
• Lightweight data indexing and compression in external memory
• Lightweight LCP construction for very large collections of strings
• Lightweight data indexing and compression in external memory
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Comparing DNA sequence collections by direct comparison of compressed text indexes
• Prefix-free parsing for building big BWTs
• A new class of string transformations for compressed text indexing

Describes a project that uses

Uses Software

• SRA

This page was built for publication: Lightweight BWT construction for very large string collections

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