Searching for (nearly) exact matches

Hash

Suffix arrays

Suffix trees

4N ~ = Genome length

N=word length (for “lookup”)

e.g. Set aside space for

416 ~ = 4 billion genomic positions (each requires 4-bytes of storage).

Previous slide

Next slide

Back to first slide

View graphic version