KeBaB: $k$-mer based breaking for finding long MEMs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910996523646976 |
|---|---|
| author | Brown, Nathaniel K. Depuydt, Lore Zakeri, Mohsen Alhadi, Anas Allam, Nour Begleiter, Dove Karpagavalli, Nithin Bharathi Kabilan Khajjayam, Suchith Sridhar Wahed, Hamza Gagie, Travis Langmead, Ben |
| author_facet | Brown, Nathaniel K. Depuydt, Lore Zakeri, Mohsen Alhadi, Anas Allam, Nour Begleiter, Dove Karpagavalli, Nithin Bharathi Kabilan Khajjayam, Suchith Sridhar Wahed, Hamza Gagie, Travis Langmead, Ben |
| contents | Long maximal exact matches (MEMs) are used in many genomics applications such as read classification and sequence alignment. Li's ropebwt3 finds long MEMs quickly because it can often ignore much of its input. In this paper we show that a fast and space efficient $k$-mer filtration step using a Bloom filter speeds up MEM-finders such as ropebwt3 even further by letting them ignore even more. We also show experimentally that our approach can accelerate metagenomic classification without significantly hurting accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20338 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | KeBaB: $k$-mer based breaking for finding long MEMs Brown, Nathaniel K. Depuydt, Lore Zakeri, Mohsen Alhadi, Anas Allam, Nour Begleiter, Dove Karpagavalli, Nithin Bharathi Kabilan Khajjayam, Suchith Sridhar Wahed, Hamza Gagie, Travis Langmead, Ben Data Structures and Algorithms Long maximal exact matches (MEMs) are used in many genomics applications such as read classification and sequence alignment. Li's ropebwt3 finds long MEMs quickly because it can often ignore much of its input. In this paper we show that a fast and space efficient $k$-mer filtration step using a Bloom filter speeds up MEM-finders such as ropebwt3 even further by letting them ignore even more. We also show experimentally that our approach can accelerate metagenomic classification without significantly hurting accuracy. |
| title | KeBaB: $k$-mer based breaking for finding long MEMs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.20338 |