When building Burrows-Wheeler Transforms (BWTs) of truly huge datasets, prefix-free parsing (PFP) can use an unreasonable amount of memory. In this paper we show how if a dataset can be broken down into small datasets that are not very similar to each other—such as collections of many copies of genomes of each of several species, or collections of many copies of each of the human chromosomes—then we can drastically reduce PFP’s memory footprint by building the BWTs of the small datasets and then merging them into the BWT of the whole dataset.
Prefix-Free Parsing for Merging Big BWTs
Travis Gagie;Zsuzsanna Lipták;Francesco Masillo;
2025-01-01
Abstract
When building Burrows-Wheeler Transforms (BWTs) of truly huge datasets, prefix-free parsing (PFP) can use an unreasonable amount of memory. In this paper we show how if a dataset can be broken down into small datasets that are not very similar to each other—such as collections of many copies of genomes of each of several species, or collections of many copies of each of the human chromosomes—then we can drastically reduce PFP’s memory footprint by building the BWTs of the small datasets and then merging them into the BWT of the whole dataset.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
