High-performance sequence processing
PhD Thesis
Abstract
Introduction
1
Comparing genomic sequences
2
Comparing using k‑mers
3
Sketching sequences
4
Sampling with minimizers
High-performance sequence processing
5
A primer on vectorization
6
Vectorized sequence parsing
7
Rolling hashes on sequences
8
Vectorized computation of minimizers
9
Application to sequence filtering
Discussion
Locality-preserving representations of k‑mer sets
10
Background on k‑mer sets
11
Necklaces and minimizers
12
Set representation and operations
13
Super‑k‑mers maps
14
Sketching super‑k‑mers
Discussion
Sampling k‑mers to lower memory & complexity
15
Background on low density minimizers
16
Multiminimizers
17
Locally-consistent phrases
18
Lexicographic-informed sampling
Discussion
Discussion & conclusion
References
Appendices
A
Vectorized sequence parsing
B
A forward scheme for canonical minimizers
High-performance sequence processing
All we have to decide is what to do with the cycles that are given us.
not J. R. R. Tolkien
Parsing
Parsing
Hashing
Hashing
Parsing->Hashing
Minimizers
Minimizers
Hashing->Minimizers
Downstream application
Downstream application
Minimizers->Downstream application
4
Sampling with minimizers
5
A primer on vectorization