Assembly using Euler Tour

[Anshuj Garg]

Hello,
I am working on "DNA sequence assembly using Euler tour" problem. The algorithms that use euler tour technique generally involve 4 steps:
1. K-mer extractions.
2. De-bruijn graph construction.
3. Euler tour construction.
4. Contig Generation.

I understood till step-2. But the problem is, the graph that is formed using k-mers is not balanced and to find euler tour the graph should be balanced (each vertices in-degree = out-degree). I am not able to understand how the algorithms construct a euler tour when the graph is not balance. Also, the output of a assembler is a set of contigs, How these set of contigs are generated from a single de bruijn graph. How we are getting contigs from euler tour. Please Help.

[GenoMax]

This thread has some interesting links: http://seqanswers.com/forums/showthread.php?t=21573

[lh3]

Finding the Euler tour is only of theoretical interest but of little practical use. So far as I know, most main-stream assemblers do not attempt to find an Eulerian circuit. They just concatenate nodes/edges whose in- and out-degree are both 1. The concatenated segments are contigs. An Eulerian tour gives you the entire genome, in theory, not contigs.

If you just think a pure theoretical problem, on a de Bruijn graph, you would like to solve a Chinese postman problem, a generalized Eulerian problem. Actually a more proper way is to determine the traversal counts of each edge. There are other theoretical papers on these problems.

[Anshuj Garg]

Thanks a lot for your replies.....