2026-08-15T20:12:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9304 2024-03-06T10:44:00Z ddc:004 open_access

Prefix-Free Parsing for Building Big BWTs Boucher, Christina Gagie, Travis Kuhnle, Alan Manzini, Giovanni Burrows-Wheeler Transform prefix-free parsing compression-aware algorithms genomic databases High-throughput sequencing technologies have led to explosive growth of genomic databases; one of which will soon reach hundreds of terabytes. For many applications we want to build and store indexes of these databases but constructing such indexes is a challenge. Fortunately, many of these genomic databases are highly-repetitive - a characteristic that can be exploited and enable the computation of the Burrows-Wheeler Transform (BWT), which underlies many popular indexes. In this paper, we introduce a preprocessing algorithm, referred to as prefix-free parsing, that takes a text T as input, and in one-pass generates a dictionary D and a parse P of T with the property that the BWT of T can be constructed from D and P using workspace proportional to their total size and O(|T|)-time. Our experiments show that D and P are significantly smaller than T in practice, and thus, can fit in a reasonable internal memory even when T is very large. Therefore, prefix-free parsing eases BWT construction, which is pertinent to many bioinformatics applications. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christina Boucher and Travis Gagie and Alan Kuhnle and Giovanni Manzini 2018 Is Part Of LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2018.2 urn:nbn:de:0030-drops-93044 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.2 eng https://creativecommons.org/licenses/by/3.0/legalcode