Algorithms to compute the Burrows-Wheeler similarity distribution

DOI10.1016/J.TCS.2019.03.012zbMATH Open1423.68621arXiv1903.10583OpenAlexW2920807403WikidataQ128232643 ScholiaQ128232643MaRDI QIDQ2420649FDOQ2420649

Authors: Yanyan Li 

Publication date: 6 June 2019

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

Abstract: The Burrows-Wheeler transform (BWT) is a well studied text transformation widely used in data compression and text indexing. The BWT of two strings can also provide similarity measures between them, based on the observation that the more their symbols are intermixed in the transformation, the more the strings are similar. In this article we present two new algorithms to compute similarity measures based on the BWT for string collections. In particular, we present practical and theoretical improvements to the computation of the Burrows-Wheeler similarity distribution for all pairs of strings in a collection. Our algorithms take advantage of the BWT computed for the concatenation of all strings, and use compressed data structures that allow reducing the running time with a small memory footprint, as shown by a set of experiments with real and artificial datasets.

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

Recommendations

• Computing Burrows-Wheeler similarity distributions for string collections
• The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Average linear time and compressed space construction of the Burrows-Wheeler transform
• An extension of the Burrows-Wheeler transform

zbMATH Keywords

parallel algorithmscompressed data structuresBurrows-Wheeler transformstring similaritystring collections

Mathematics Subject Classification ID

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

Cites Work

• Compressed representations of sequences and full-text indexes
• Indexing compressed text
• Title not available (Why is that?)
• Practical entropy-compressed rank/select dictionary
• Suffix Arrays: A New Method for On-Line String Searches
• Fast construction of wavelet trees
• Title not available (Why is that?)
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform
• Combinatorial Pattern Matching
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• A new combinatorial approach to sequence comparison
• A Compressed Enhanced Suffix Array Supporting Fast String Matching
• Space-efficient construction of compressed indexes in deterministic linear time
• Combinatorial Pattern Matching
• Inducing enhanced suffix arrays for string collections
• Measuring the clustering effect of BWT via RLE
• Computing Burrows-Wheeler similarity distributions for string collections

Cited In (5)

• A comparison of BWT approaches to string pattern matching
• A simple algorithm for computing the document array
• The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform
• Comparative genomics with succinct colored de Bruijn graphs
• Computing Burrows-Wheeler similarity distributions for string collections

This page was built for publication: Algorithms to compute the Burrows-Wheeler similarity distribution

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