In this thesis, we focus on the problem of reconstructing haplotypes for polyploid genomes and the utilization of called haplotypes in de novo assembly of these genomes. We approach this topic exploring short read sequence data of the highly heterozygous hexaploid sweet potato genome. First, we investigate the role of heterozygosity and ploidy number in reconstructing haplotypes with short reads. In short, higher heterozygosity provides higher number of useful reads for reconstructing haplotypes while being polyploid introduces a challenge in assembling reads into longer sequences; we called it the problem of Ambiguity of Merging fragments. However, we address this problem and show that reads can be assembled into haplotypes with high accuracy using short reads. To this end, we propose a new algorithm, called Ranbow, and evaluate its performance on real and simulated datasets from tetraploid Capsella bursa-pastoris (Shepherd's Purse), and hexaploid Ipomoea batatas (sweet potato) genomes. We are able to show that our method achieves higher accuracy and longer assembled haplotypes than the other methods. Next, we present the de novo assembly pipeline of the sweet potato genome utilizing computed haplotypes for genome assembly improvement. This novel approach, called haplo-scaffolders, uses the assembled haplotypes in order to rescue a set of potential connections which were hidden due to the differences of true haplotypes and the reference sequence. These connections are obtained by mapping the reads into haplotypes and transforming the connection information to the reference level. This process can be repeated by updating the scaffold set to further improve the genome assembly. We show that this strategy improves substantially the N50 and maximum scaffold length of assembled sweet potato genome.
Diese Dissertation widmet sich dem Problem der Rekonstruktion von Haplotypen in polyploiden Genomen, und der Verwendung der Haplotypen für das “de novo assembly" dieser Genome. Der gewählte Ansatz stützt sich auf “short read" Sequenzierdaten des höchst heterozygoten hexaploiden Genoms der Süßkartoffel. Zunächst wird die Rolle der Heterozygosität und Ploidie im Kontext der Rekonstruktion von Haplotypen durch "short reads" untersucht. Höhere Heterozygosität macht mehr "reads" für die Rekonstruktion von Haplotypen nutzbar, während die Polyploidie das Zusammenfügen der reads in längere Sequenzen erschwert. Dieses Problem wird hier "Ambiguity of Merging Fragments" genannt und durch den beschriebenen Algorithmus Ranbow adressiert. Die Leistung von Ranbow wird mit Hilfe von realen und simulierten Datensätzen des tetraploiden Genoms des Hirtentäschelkrauts ("Capsella bursa-pastoris") und des hexaploiden Genoms der Süßkartoffel ("Ipomoea batatas") evaluiert. Der Vergleich mit anderen Methoden zeigt, dass man mit Ranbow die höchste Genauigkeit und die längsten Haplotypen erreicht. Anschließend wird eine Pipeline für das verbesserte "de novo assembly" des Süßkartoffelgenoms präsentiert, die die zuvor errechneten Haplotypen nutzt. Diese neue Methode, genannt "haplo-scaffolders", deckt mit Hilfe der Haplotypen einen Satz an möglichen Verbindungen zwischen "scaffolds" auf, die zuvor durch die Unterschiede zwischen echten Haplotypen und der Referenzsequenz versteckt blieben. Diese Verbindungen werden aufgedeckt, indem die "reads" den Haplotypen zugeordnet werden und die Verbindungen auf das Referenzlevel übertragen werden. Der Prozess kann wiederholt werden, in dem der "scaffold" Satz aktualisiert wird, um das Genom “assembly" weiter zu verbessern. Es wird gezeigt, dass diese Strategie den N50-Wert und die maximale Scaffold-Länge des Süßkartoffelgenoms signifikant verbessern.
