We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing.
- Authors
Orenstein, Yaron; Pellow, David; Marçais, Guillaume; Shamir, Ron; Kingsford, Carl
- Abstract
With the rapidly increasing volume of deep sequencing data, more efficient algorithms and data structures are needed. Minimizers are a central recent paradigm that has improved various sequence analysis tasks, including hashing for faster read overlap detection, sparse suffix arrays for creating smaller indexes, and Bloom filters for speeding up sequence search. Here, we propose an alternative paradigm that can lead to substantial further improvement in these and other tasks. For integers k and L > k, we say that a set of k-mers is a universal hitting set (UHS) if every possible L-long sequence must contain a k-mer from the set. We develop a heuristic called DOCKS to find a compact UHS, which works in two phases: The first phase is solved optimally, and for the second we propose several efficient heuristics, trading set size for speed and memory. The use of heuristics is motivated by showing the NP-hardness of a closely related problem. We show that DOCKS works well in practice and produces UHSs that are very close to a theoretical lower bound. We present results for various values of k and L and by applying them to real genomes show that UHSs indeed improve over minimizers. In particular, DOCKS uses less than 30% of the 10-mers needed to span the human genome compared to minimizers. The software and computed UHSs are freely available at github.com/Shamir-Lab/DOCKS/ and acgt.cs.tau.ac.il/docks/, respectively. In this work, we create universal κ-mer hitting sets that hit any L-long sequence. We present several heuristic approaches for constructing such small sets; the approaches vary in the trade-off between the size of the produced set and runtime and memory usage. We show the benefit in practice of using the produced universal κ-mer hitting sets compared to minimizers and randomly created hitting sets on the human genome.:
- Subjects
HUMAN genome; HEURISTIC; BLOOM syndrome; GENETIC disorders; SEQUENCE (Linguistics); HUMAN chromosomes
- Publication
PLoS Computational Biology, 2017, Vol 13, Issue 10, p1
- ISSN
1553-734X
- Publication type
Article
- DOI
10.1371/journal.pcbi.1005777