Wheeler graphs: a framework for BWT-based data structures
From MaRDI portal
Publication:1676308
DOI10.1016/j.tcs.2017.06.016zbMath1380.68145OpenAlexW2725379159WikidataQ47136623 ScholiaQ47136623MaRDI QIDQ1676308
Jouni Sirén, Travis Gagie, Giovanni Manzini
Publication date: 6 November 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.06.016
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (30)
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Can formal languages help pangenomics to represent and analyze multiple genomes? ⋮ The complexity of approximate pattern matching on de Bruijn graphs ⋮ A new class of string transformations for compressed text indexing ⋮ On the Complexity of String Matching for Graphs ⋮ Efficient construction of the BWT for repetitive text using string compression ⋮ Algorithms and complexity on indexing founder graphs ⋮ On representing the degree sequences of sublogarithmic-degree Wheeler graphs ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs ⋮ Colored constrained spanning tree on directed graphs ⋮ Ordering regular languages and automata: complexity ⋮ Computational graph pangenomics: a tutorial on data structures and their applications ⋮ Unnamed Item ⋮ A faster implementation of online RLBWT and its application to LZ77 parsing ⋮ When a dollar makes a BWT ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Succinct representations for (non)deterministic finite automata ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ Lightweight merging of compressed indices based on BWT variants ⋮ The alternating BWT: an algorithmic perspective ⋮ Wheeler languages ⋮ A new class of searchable and provably highly compressible string transformations ⋮ Haplotype-aware graph indexes ⋮ Succinct representation for (non)deterministic finite automata ⋮ Solving string problems on graphs using the labeled direct product ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs ⋮ On the complexity of recognizing Wheeler graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Approximate string matching using a bidirectional index
- FM-index of alignment: a compressed index for similar strings
- Lightweight algorithms for constructing and inverting the BWT of string collections
- New algorithms on wavelet trees and applications to information retrieval
- A bijection between words and multisets of necklaces
- Counting permutations with given cycle structure and descent set
- The myriad virtues of wavelet trees
- An extension of the Burrows-Wheeler transform
- Bidirectional Variable-Order de Bruijn Graphs
- Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform
- Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis
- Compressed representations of sequences and full-text indexes
- Succinct Indexes for Circular Patterns
- The compressed permuterm index
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- An analysis of the Burrows—Wheeler transform
- Compressing and indexing labeled trees, with applications
- Boosting textual compression in optimal linear time
- Indexing compressed text
- pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
- Succinct de Bruijn Graphs
- An Encoding for Order-Preserving Matching.
- Indexing Variation Graphs
- Compressed text indexes
- Combinatorial Pattern Matching
This page was built for publication: Wheeler graphs: a framework for BWT-based data structures
