A near-tight lower bound on the density of forward sampling schemes
Bryce Kille, Ragnar Groot Koerkamp, Drake McAdams, Alan Liu, Todd J Treangen, Yann Ponty · 2024
Read A near-tight lower bound on the density of forward sampling schemes by Bryce Kille, Ragnar Groot Koerkamp, Drake McAdams, Alan Liu, Todd J Treangen, Yann Ponty (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/pmc-11676336.txt.
Description
Bryce Kille and co-authors wrote this 2024 paper on a core task in DNA sequence analysis. Many tools sample short DNA chunks called k-mers instead of reading every chunk. Good sampling schemes keep few chunks while still catching at least one in each short window of the sequence.
The team proved a lower bound on how few chunks any forward sampling scheme can keep. For small window and chunk sizes, the bound is exact in a common case. Their result shows that top current schemes sit much closer to the best possible density than was known. For one standard setting in the minimap2 tool, the best scheme is at most 3 percent denser than ideal, down from a past gap of 50 percent.
Catalog record
| CREATOR | Bryce Kille, Ragnar Groot Koerkamp, Drake McAdams, Alan Liu, Todd J Treangen, Yann Ponty |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |