String Partition for Building Long Burrows-Wheeler Transforms
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909609786081280 |
|---|---|
| author | Adler, Enno Böttcher, Stefan Hartel, Rita |
| author_facet | Adler, Enno Böttcher, Stefan Hartel, Rita |
| contents | Constructing the Burrows-Wheeler transform (BWT) for long strings poses significant challenges regarding construction time and memory usage. We use a prefix of the suffix array to partition a long string into shorter substrings, thereby enabling the use of multi-string BWT construction algorithms to process these partitions fast. We provide an implementation, partDNA, for DNA sequences. Through comparison with state-of-the-art BWT construction algorithms, we show that partDNA with IBB offers a novel trade-off for construction time and memory usage for BWT construction on real genome datasets. Beyond this, the proposed partitioning strategy is applicable to strings of any alphabet. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_10610 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | String Partition for Building Long Burrows-Wheeler Transforms Adler, Enno Böttcher, Stefan Hartel, Rita Data Structures and Algorithms Constructing the Burrows-Wheeler transform (BWT) for long strings poses significant challenges regarding construction time and memory usage. We use a prefix of the suffix array to partition a long string into shorter substrings, thereby enabling the use of multi-string BWT construction algorithms to process these partitions fast. We provide an implementation, partDNA, for DNA sequences. Through comparison with state-of-the-art BWT construction algorithms, we show that partDNA with IBB offers a novel trade-off for construction time and memory usage for BWT construction on real genome datasets. Beyond this, the proposed partitioning strategy is applicable to strings of any alphabet. |
| title | String Partition for Building Long Burrows-Wheeler Transforms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.10610 |