How k-mers are merged to form contigs

[kdarbs]

I have a perl code that generates all k-mers of a sequence. Now, am trying to get contigs using these k-mers.

Does anybody have an idea how contigs are generated from k-mers in perl or any other language.

Thank you!

[atcghelix]

de Bruijn graphs are used for this in many assembly programs nowadays.

I've never actually seen them implemented in Perl, but I'd be interested if you find an example. I may be writing an example in Perl soon. It seems like it could be fairly straightforward. I think you might end up having to search for partial hash key matches (assuming you have made a hash of your kmer sequences). To do that you can use something like Tie::Hash::Regex, or the smart match operator. Actually the smart match operator (~~) seems like it'd be perfect for this, but I'd be too afraid to use it if you want the code to work on other computers with different versions of Perl or on computers that might be upgraded--it sounds like they may be drastically changing its behavior soon. See: http://stackoverflow.com/questions/5...lar-expression

One of the links below contains a Python implementation, but I haven't looked at it to see if it works, etc...

These might get you started:
http://vort.org/2010/10/29/fun-de-bruijn-graphs/
http://www.nature.com/nbt/journal/v2.../nbt.2023.html
http://www.homolog.us/Tutorials/index.php?p=1.1&s=1

[kdarbs]

Thank you!