Reference Graph Construction and Merging for Human Genomic Sequences

Abstract

The focus of this thesis is on the computational challenges faced when reading out human DNA. In particular, the reads of the DNA are commonly aligned with the help of a reference string. In this thesis, the opportunities and difficulties when using a graph reference instead are explored.Several approaches for using graph references have already been proposed, but none of them are used widely in this field. Therefore here we compare the existing approaches and develop new algorithms for working with genomic graphs. This is intended to further help spread the usage of graph references. In particular, we develop algorithms for merging and fusing flat XBW tables, which represent genomic graphs. We implement these algorithms in the Graph Merging Library GML, which can be used to visualize their behaviour to further the understanding of these methods. In addition to being used for the alignment of reads to reference graphs, genomic graphs can also arise in other situations. Our newly developed algorithms are general enough to also be of use in these scenarios.Overall, this thesis constitutes a step in the direction of adopting the more complicated but more powerful graphs rather than sequential string data within the field of DNA sequencing.

Markmið þessarar ritgerðar er að varpa ljósi á þær áskoranir í tölvunarfræði sem verða til við raðgreiningu á DNA úr mönnum. Venjulega er DNA röðum samraðað með hjálp strengjatilvísana. Í þessari ritgerð verða hinsvegar tækifæri og vandamál með notkun netatilvísana skoðuð.Stungið hefur verið upp á nokkrum leiðum til að nota netatilvísanir en slíkar aðferðir hafa enn ekki komist í almenna notkun. Við berum því saman núverandi nálganir og þróum ný reiknirit til að vinna með erfðamengisnet. Markmiðið er að hjálpa til við að útbreiða notkun á netatilvísunum og höfum við þróað reiknrit sem að sameina og samtvinna flatar XBW töflur sem hafa að geyma erfðamengisnet. Við höfum útfært þessi reiknirit í forritunarsafninu Graph Merging Library (GML) og er hægt í því að sýna á myndrænan hátt hvernig þau virka og auka skilning okkar á þeim. Auk þess að nota þau til samröðunar á raðgreiningargögnum með hjálp netatilvísana geta erfðamengisnet nýst annara hluta. Reiknritin eru næginlega almenn til að nýtast í þeim tilfellum.Á heildina litið er þessi ritgerð skref í átt að koma í notkun flóknari og öflugri netum í stað þess að nota línulega strengi á fyrir samröðun á DNA.