Algorithms for de novo assembly of large genomes.

disertacija

• Naslov (hrvatski): Algoritmi za de novo sastavljanje velikih genoma.
• Autor: Robert Vaser
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; (Zavod za elektroničke sustave i obradbu informacija); Zagreb
• Datum i država obrane: 2019, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo; Obradba informacija
• Univerzalna decimalna klasifikacija (UDC): 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka

Sažetak

The inability of DNA sequencing technologies to interpret entire molecules led to the development of methods that connect the obtained short fragments back together in a puzzle-like process. They are called assemblers and their design is guided with the notion that similar fragments originate from the same genomic region. That is often annulled due to sequencing errors and repetitive nature of the genome. The advent of new sequencing approaches, namely Pacific Biosciences and Oxford Nanopore Technologies, pushed the limit on the fragment lengths at a cost of higher error rates, but still facilitated the assembly problem considerably. First assembly attempts used various types of error correction approaches prior the assembly with existing tools at that time. Although, several long read based assemblers have been proposed in the past years, they demand significant amounts of computational resources. The focus of this research is development of memory efficient and scalable algorithms for de novo assembly of large genomes using raw third generation of sequencing data. In the scope of the thesis we implemented three novel tools for genome assembly: a memory friendly layout module called Rala, which builds the assembly graph from preprocessed sequences and resolves junctions in graph with the help of force directed placement; a fast and accurate consensus module called Racon based on vectorized partial order alignment; and the complete de novo assembler called Raven, which competes with state-of-the-art assemblers both in quality and resource management.

Sažetak (hrvatski)

Tehnologije za sekvenciranje genoma nisu u mogućnosti interpretirati DNA molekule u cijelosti te je to dovelo do razvoja računalnih metoda koje spajaju kratke fragmente u procesu koji podsjeća na rješavanje slagalica. Alati namijenjeni za ovaj problem nazivaju se asembleri čiji je dizajn baziran na pretpostavci da slični fragmenti potječu iz iste regije genoma. Ta pretpostavka je često poništena zbog pogrešaka prilikom sekvenciranja te repetitivne prirode genoma. Pojava novih tehnologija za sekvenciranje tvrtki Pacific Biosciences i Oxford Nanopore Technologies olakšala je problem sastavljanja genoma zahvaljujući znatno većoj duljini dobivenih fragmenata, ali uz nedostatak veće pogreške. Iako nekoliko asemblera za dugačke fragmente već postoji, oni zahtijevaju pozamašne količine računalnih resursa. Fokus ovog istraživanja je razvoj memorijskih efikasnih i skalabilnih algoritama za de novo sastavljanje velikih genoma, pritom koristeći podatke treće generacije sekvenciranja. U sklopu ove disertacije implementirana su tri nova alata za sastavljanje genoma: memorijski učinkovita faza razmještaja zvana Rala, koja gradi graf sastavljanja iz skupa filtriranih fragmenata te ga pojednostavljuje koristeći algoritam razmještaja simulacijom djelovanja silama; brza i točna faza konsenzusa zvana Racon, koja je bazirana na vektoriziranom poravnanju parcijalnog uređaja; te cjelokupan de novo asembler nazvan Raven, koji konkurira s trenutno najefikasnijim poznatim metodama u kvaliteti i upravljanju resursima.

• Ključne riječi: de novo; assembly; long reads; PacBio; Oxford Nanopore; pile-o-gram; partial order alignment; force directed layout; vectorization
• Ključne riječi (hrvatski): de novo; sastavljanje; dugačka očitanja; PacBio; Oxford Nanopore; gomila preklapanja; razmještaj simulacijom djelovanja sila; poravnanje parcijalnog uređaja; vektorizacija
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:043873
• Studijski program: Naziv: Elektrotehnika i računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski doktorski; Akademski / stručni naziv: Doktor znanosti elektrotehnike i računarstva (dr.sc.)
• Vrsta resursa: Tekst
• Opseg: 83 str. ; 30 cm
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2020-01-29 13:03:08