Genomic Dna Hash Tables And Ambiguous Bases

Question

[Gww]

Hi,

I'm hoping to implement a genomic DNA hash-table and I unsure how to handle N bases?

Should I skip the k-mers that contain them? or generate the possible sequences up to a limit of X N's per k-mer?

EDIT:

I'm hoping to use the hash table to find perfect k-mer matches within the human genome (I'm aiming for a k-mer size of 10-12 nucleotides). My query sequences won't have ambiguous bases so I'm not too worried about dealing with those. I assume the best strategy is to just skip sequences that have N's.

Thanks

Answer 1

[Gingi]

Yes, if you're looking for perfect matches, don't index kmers that contain Ns.

Are you coding the kmer index yourself? You might want to take a look at Tallymer, which creates an index similar to what you have in mind.

[Gww]

Thanks for the advice, I want to code it myself mostly for the learning experience (I haven't written a hash table before). But that link will be really helpful.

Answer 2

[brentp]

You'll probably get more useful answers if you indicate your intended use of the hash-table.

Meanwhile check this thread to see how existing software handles the problem.

As another datapoint bowtie just treats non-ACGT characters in a read as mismatches--but it's not using a hash.

[lh3]

Strictly speaking, bowtie treats an ambiguous base as a random base in mapping. It corrects for that afterwards, but this is different from building the ambiguity in the index.

[Gww]

Thanks for the answer, I updated my question with a bit more information regarding my goals. Oh PS. I really enjoyed your blog article on bloom filters :).

[brentp]

@lh3, aye, but that's in the reference. at least according to the docs:"Ambiguous characters in the read mismatch all other characters."