Introduction

De Bruijn graph-based algorithms solve the genome assembly problem in two steps. First, a de Bruijn graph is constructed from all sequencing reads. Next the de Bruijn graph is traversed to determine its underlying genome sequence. So far, we studied the inverse of second step by constructing de Bruijn graph from a known genome. In case of assembly, the genome itself is unknown and needs to be figured out. In this section, we will look at that assembly process, but for simplicity, we will consider reads to be perfect and discuss sequencing imperfections in the following section.