Der Ansatz der DNA-Sequenzierung, der 1977 zum Zusammenbau eines kleinen Virus führte, durchlief eine Reihe von Veränderungen, die vor einigen Jahren zum Aufkommen der personalisierten Medizin beitrugen. Ende der 1980er Jahre sequenzierten Biologen routinemäßig virale Genome mit Hunderttausenden von Nukleotiden, aber die Idee, ein bakterielles (geschweige denn ein menschliches) Genom mit Millionen (oder gar Milliarden) von Nukleotiden zu sequenzieren, blieb absurd und würde Milliarden von Dollar kosten. 1988 hatten drei Biologen (unabhängig voneinander und gleichzeitig!) eine Idee zur Senkung der Sequenzierungskosten und schlugen die futuristische und damals völlig unglaubwürdige Methode der DNA-Arrays vor. Keiner dieser drei Biologen hätte sich vorstellen können, dass die Implikationen seiner eigenen experimentellen Forschung ihn schließlich mit herausfordernden algorithmischen Problemen konfrontieren würden. In diesem Modul lernen Sie die algorithmische Herausforderung der DNA-Sequenzierung anhand der Informationen über kurze k-mere kennen, die von DNA-Arrays geliefert werden. Außerdem reisen Sie ins 18. Jahrhundert, um etwas über die Brücken von Königsberg zu erfahren und ein damit zusammenhängendes Problem zu lösen: das Zusammensetzen eines Puzzles!

Unsere Diskussion über den Zusammenbau von Genomen beruhte bisher auf verschiedenen Annahmen. In diesem Modul werden wir uns mit den praktischen Herausforderungen auseinandersetzen, die durch die Macken der modernen Sequenzierungstechnologien entstehen, und einige algorithmische Techniken diskutieren, die entwickelt wurden, um diese Herausforderungen zu meistern. Anschließend werden Sie das kleinste bakterielle Genom zusammensetzen, das symbiotisch in Heuschrecken lebt. Sein geschütztes Leben hat es ihm ermöglicht, sein Genom auf nur 112.091 Nukleotide und 137 Gene zu reduzieren. Und danach sind Sie bereit, das Genom von E. coli X zu assemblieren!