2026-07-23T05:31:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18736 2024-03-06T11:02:36Z ddc:004 open_access

Matching Statistics Speed up BWT Construction Masillo, Francesco Burrows-Wheeler Transform matching statistics string collections compressed representation data structures efficient algorithms Due to the exponential growth of genomic data, constructing dedicated data structures has become the principal bottleneck in common bioinformatics applications. In particular, the Burrows-Wheeler Transform (BWT) is the basis of some of the most popular self-indexes for genomic data, due to its known favourable behaviour on repetitive data. Some tools that exploit the intrinsic repetitiveness of biological data have risen in popularity, due to their speed and low space consumption. We introduce a new algorithm for computing the BWT, which takes advantage of the redundancy of the data through a compressed version of matching statistics, the CMS of [Lipták et al., WABI 2022]. We show that it suffices to sort a small subset of suffixes, lowering both computation time and space. Our result is due to a new insight which links the so-called insert-heads of [Lipták et al., WABI 2022] to the well-known run boundaries of the BWT. We give two implementations of our algorithm, called CMS-BWT, both competitive in our experimental validation on highly repetitive real-life datasets. In most cases, they outperform other tools w.r.t. running time, trading off a higher memory footprint, which, however, is still considerably smaller than the total size of the input data. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Francesco Masillo 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.83 urn:nbn:de:0030-drops-187360 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.83 eng https://creativecommons.org/licenses/by/4.0/legalcode