Scroll
Bioinformatics Research
Classifying DNA fragments is hard
Large amounts of data means searching through enormous collections of genomic information
A solution is using Bitvectors
Bitvectors store this data in a compact, easy to search way.
Genomic information
A C G T G A C C T A G C T G A A C T G C
↓
0 1 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1
Compact representation · bit vector
The next problem
How do we find
How do we find
anything in here?
rank(1, i) → number of 1s before position i
Don't count
everything
Store checkpoints so a query can jump close to its destination instead of scanning from the beginning.
Paired bit-vector layout
Jump, Jump, Count
64K Superblock · 01
512
512
512
512
512
512
512
512
64K Superblock · 02
512
512
512
512
512
512
512
512
64K Superblock · 03
512
512
512
512
512
512
512
512
Rank Query
position
83,412
superblock
02
block
06
local scan
140 bits
rank
41,728
Song Li Lab · Dartmouth College
High-performance
High-performance
genomic classification
In this research I worked on large-scale metagenomic classification in C++. I developed a paired bit-vector data structure designed to reduce storage overhead while preserving fast rank queries.