Fragment assembly.

<p>(A–C) Hamiltonian. (A) A sequence with overlapping reads; (B) Each read is represented as a vertex, with edges connecting the overlapping vertices; (C) the assembly solution is a Hamiltonian path (all vertices are visited, no vertex is visited more than once) through the resulting graph; (D) For short reads assembly, each vertex is a <i>k</i>-mer (or a hashed collection of <i>k</i>-mers), and the reads are threaded between vertices as edges. The solution is a Eulerian path, where each edge is visited once. Repeats are merged into a single edge. For detailed algorithms see <a href="http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.1000667#pcbi.1000667-Pevzner1" target="_blank">[49]</a>, <a href="http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.1000667#pcbi.1000667-Chaisson1" target="_blank">[50]</a>, <a href="http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.1000667#pcbi.1000667-Zerbino1" target="_blank">[53]</a>–<a href="http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.1000667#pcbi.1000667-Warren1" target="_blank">[55]</a>.