Comparing DNA sequence collections by direct comparison of compressed text indexes

DOI10.1007/978-3-642-33122-0_17MaRDI QIDQ4916910zbMATH OpenOpenAlexFDO

Authors Anthony J. Cox, T. Jakobi, Giovanna Rosone, Ole B. Schulz-Trieglaff

Publication date 26 April 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Popular sequence alignment tools such as BWA convert a reference genome to an indexing data structure based on the Burrows-Wheeler Transform (BWT), from which matches to individual query sequences can be rapidly determined. However the utility of also indexing the query sequences themselves remains relatively unexplored. Here we show that an all-against-all comparison of two sequence collections can be computed from the BWT of each collection with the BWTs held entirely in external memory, i.e. on disk and not in RAM. As an application of this technique, we show that BWTs of transcriptomic and genomic reads can be compared to obtain reference-free predictions of splice junctions that have high overlap with results from more standard reference-based methods. Code to construct and compare the BWT of large genomic data sets is available at http://beetl.github.com/BEETL/ as part of the BEETL library.

Recommendations

• scientific article; zbMATH DE number 7716299
• Lightweight BWT construction for very large string collections
• Lightweight algorithms for constructing and inverting the BWT of string collections
• An Experimental Study of Compressed Indexing and Local Alignments of DNA
• Detecting mutations by eBWT

Cited in

(9)

• Detecting mutations by eBWT
• The Burrows-Wheeler transform between data compression and combinatorics on words
• When a dollar makes a BWT
• An external-memory algorithm for string graph construction
• Comparison of BWA-MEM and NovoAlign using human whole-genome next-generation sequencing reads
• BEETL
• An Experimental Study of Compressed Indexing and Local Alignments of DNA
• A head-to-head comparison of de Bruijn indices and names
• Generalized substring compression

Describes a project that uses

Uses Software

• GitHub
• BEDTools
• TopHat
• Soap

This page was built for publication: Comparing DNA sequence collections by direct comparison of compressed text indexes

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