Compressed directed acyclic word graph with application in local alignment

DOI10.1007/S00453-013-9794-ZMaRDI QIDQ378207zbMATH OpenOpenAlexFDO

Authors Huy Hoang Do, Wing-Kin Sung

Publication date 11 November 2013

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-013-9794-z

zbMATH Keywords

compressionsuffix treesuffix arraydirected acyclic word graphlocal alignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Compressed directed acyclic word graph with application in local alignment
• Compact directed acyclic word graphs for a sliding window
• Compact morphic directed acyclic word graphs
• On Sensitivity of Compact Directed Acyclic Word Graphs
• Locally compressed suffix arrays
• Dynamic dictionary matching and compressed suffix trees
• scientific article; zbMATH DE number 1786457
• On-line construction of compact directed acyclic word graphs

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Average-case analysis of approximate trie search
• Compressed suffix trees with full functionality
• Indexing compressed text
• Rank/select operations on large alphabets
• SOFSEM 2005: Theory and Practice of Computer Science
• Suffix Arrays: A New Method for On-Line String Searches
• The smallest automaton recognizing the subwords of a text
• Ultra-succinct representation of ordered trees with applications

Cited in

(2)

• An Experimental Study of Compressed Indexing and Local Alignments of DNA
• Compressed directed acyclic word graph with application in local alignment

Describes a project that uses

Uses Software

• REPuter
• BWA

This page was built for publication: Compressed directed acyclic word graph with application in local alignment

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