I've been asked to evaluate whether the MinION will be sufficient to distinguish between 20bp CRISPR guide RNAs from the GeCKO v2 set. I know that this set has some exactly identical sequences, which wouldn't be distinguishable regardless of the sequencing method used, so I would like to know whether any two non-indentical sequences differ by less than 15% of the 20bp (i.e. only 3 bases different).
There are around 130k 20bp sequences in the dataset, and I'm pretty sure that an all-vs-all approach is not feasible, but perhaps there's some trick that I'm missing.
What I thought of doing was looking at dimer and trimer/codon counts to hunt down sequences that were most similar. I found about 100 sequences that shared the same trimer count signature (but were not identical), and within this group found [only] one pair with 85% identity; all the remainder were 70% or less.
... but I'm having trouble ignoring the doubt I have that these two sequences are the most similar. It might be possible that there are sequences in the dataset that don't have identical trimer count signatures, but differ by less than three bases. I'll give a very obvious example (which isn't in the dataset):
1: AAAAA AAAAA AAAAA AAAAA 2: AAAAC AAAAA AAAAA AAAAA
The trimer counts for these two sequences are different (Sequence 1 -- AAA: 18; Sequence 2 -- AAA: 15; AAC: 1; ACA: 1; CAA: 1), and yet the sequences are only 1 base different (which might be a problem for the MinION). How can I work out if any such sequence pairs exist in the dataset?