 |
HAL-LIRMM - Open Archive |  |
Conference papers
Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding
Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding
Abstract : The boom of genomic sequencing makes compression of sets of sequences inescapable. This underlies the need for multi-string indexing data structures that helps compressing the data. The most prominent example of such data structures is the Burrows-Wheeler Transform (BWT), a reversible permutation of a text that improves its compressibility. A similar data structure, the eXtended Burrows-Wheeler Transform (XBW), is able to index a tree labelled with alphabet symbols. A link between a multi-string BWT and the Aho-Corasick automaton has already been found and led to a way to build a XBW from a multi-string BWT. We exhibit a stronger link between a multi-string BWT and a XBW by using the order of the concatenation in the multi-string. This bijective link has several applications: first, it allows one to build one data structure from the other; second, it enables one to compute an ordering of the input strings that optimises a Run-Length measure (i.e., the compressibility) of the BWT or of the XBW.
Cited literature [2 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02382066
Contributor : Eric Rivals <>
Submitted on : Wednesday, November 27, 2019 - 7:38:59 AM
Last modification on : Tuesday, March 17, 2020 - 3:26:41 AM
Long-term archiving on: : Friday, February 28, 2020 - 1:22:50 PM
Contributor : Eric Rivals <>
Submitted on : Wednesday, November 27, 2019 - 7:38:59 AM
Last modification on : Tuesday, March 17, 2020 - 3:26:41 AM
Long-term archiving on: : Friday, February 28, 2020 - 1:22:50 PM
File
LIPIcs-CPM-2019-24.pdf
Files produced by the author(s)