| Autor: |
Bonizzoni P; University of Milano-Bicocca, Milano, Italy., Boucher C; University of Florida, Gainesville, FL., Cozzi D; University of Milano-Bicocca, Milano, Italy., Gagie T; Dalhousie University, Halifax, NS, Canada., Köppl D; University of Muenster, Muenster, Germany., Rossi M; University of Florida, Gainesville, FL. |
| Jazyk: |
angličtina |
| Zdroj: |
International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium) [Int Symp String Process Inf Retr] 2023 Sep; Vol. 14240, pp. 89-101. Date of Electronic Publication: 2023 Sep 20. |
| DOI: |
10.1007/978-3-031-43980-3_8 |
| Abstrakt: |
The positional Burrows-Wheeler Transform (PBWT) was presented as a means to find set-maximal exact matches (SMEMs) in haplotype data via the computation of the divergence array. Although run-length encoding the PBWT has been previously considered, storing the divergence array along with the PBWT in a compressed manner has not been as rigorously studied. We define two queries that can be used in combination to compute SMEMs, allowing us to define smaller data structures that support one or both of these queries. We combine these data structures, enabling the PBWT and the divergence array to be stored in a manner that allows for finding SMEMs. We estimate and compare the memory usage of these data structures, leading to one data structure that is most memory efficient. Lastly, we implement this data structure and compare its performance to prior methods using various datasets taken from the 1000 Genomes Project data. |
| Databáze: |
MEDLINE |
| Externí odkaz: |
|
