Aufgrund von technisch bedingten Einschränkungen ist es nur möglich kleine Teile einer großen DNA-Sequenz zu entschlüsseln, also die Basen zu bestimmen. Werden nun viele Kopien der Ursprungssequenz statistisch geteilt und entschlüsselt, macht man sich die Überlappung einzelner Teilsequenzen zunutzte um auf die Ursprungssequenz zurückzuschließen. Dieses Szenario ist die Motivation für den zweiten, ausführlichen Teil dieser Ausarbeitung, in der man von einer idealisierten Annahme ausgeht. Es werden dann verschiedene Lösungsansätze gezeigt, die den sogenannten Shortest Superstring einer Menge von Strings bis zu einer bestimmten Fehlergrenze effizient approximieren.
Ausarbeitung (700k)