Real sequencers can't read one long genome straight through — they only produce many short, overlapping reads. To reassemble the original sequence, each read is chopped into every overlapping k-mer (substring of length k). Every unique k-mer becomes a graph node; a directed edge joins k-mer A to k-mer B whenever B was seen immediately after A in a read — i.e. they overlap by k−1 letters.
read: ACGTAGC
k=4: ACGT→CGTA→GTAG→TAGC
Reconstructing the genome means walking this graph along a path that uses every edge exactly once — an Eulerian path. If a k-mer sequence appears only once in the genome, exactly one such path exists.
The catch: if the genome contains a repeated sub-sequence longer than k, the k-mers inside it collide into shared nodes with more than one outgoing edge. The graph then admits several different Eulerian paths — all equally valid by the graph's rules, but only one matches the true genome. Short-read assemblers genuinely cannot resolve this without extra information (longer reads, paired ends, or long-read sequencing).
- k-mer length — shorter k merges more k-mers together, making branch points more likely even without a "real" repeat.
- Read length — controls how the genome is fragmented before k-mer extraction; longer reads span more of a repeat and can sometimes resolve it.