[vineetg]

I left PAM sites out of the blog post (it's actually mentioned briefly in the footnotes), as it made the problem slightly more complicated.

The final algorithm actually keeps track of the last 20 bases + PAM length, and checks both the edit distance and PAM before deciding if something is a match. The Benchling CRISPR tool will do this for you :)

[daemonk]

Couldn't you use one of the available short read aligners (BWA,bowtie...) available for this also? Most of the aligners use some kind of FM-index for indexing the genome.

[vineetg]

We messed around with bowtie - it seems like most of these are optimized for the number of alignments being small (i.e. close to 1). Unfortunately, the number of matches for a 20 base guide on the human genome is closer to 1000.