Prefix-free parsing for merging big BWTs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915330297692160 |
|---|---|
| author | Diaz-Dominguez, Diego Gagie, Travis Guerrini, Veronica Langmead, Ben Liptak, Zsuzsanna Manzini, Giovanni Masillo, Francesco Shivakumar, Vikram |
| author_facet | Diaz-Dominguez, Diego Gagie, Travis Guerrini, Veronica Langmead, Ben Liptak, Zsuzsanna Manzini, Giovanni Masillo, Francesco Shivakumar, Vikram |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03294 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Prefix-free parsing for merging big BWTs Diaz-Dominguez, Diego Gagie, Travis Guerrini, Veronica Langmead, Ben Liptak, Zsuzsanna Manzini, Giovanni Masillo, Francesco Shivakumar, Vikram Data Structures and Algorithms 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. |
| title | Prefix-free parsing for merging big BWTs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.03294 |