medvedevgroup / TwoPaCo

A fast constructor of the compressed de Bruijn graph from many genomes
Other
39 stars 10 forks source link

Implement two pass aggregation strategy #1

Closed iminkin closed 7 years ago

iminkin commented 9 years ago

First pass: enumerate all candidates, put them in a sorted array of atomic ints Second pass: binary search over the array, update the preceding/succeeding characters and set a flag if it is a bifurcating kmer

All in parallel, first pass is with a hashet with a spinlock

Or, alternatively, use a lock-free hash table http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/