Algorithms for de novo assembly of large genomes.

doctoral thesis

• Title (croatian): Algoritmi za de novo sastavljanje velikih genoma.
• Author: Robert Vaser
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Electronic Systems and Information Processing); Zagreb
• Defense date and country: 2019, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing; Data Processing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

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.

Abstract (croatian)

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.

• Keywords: de novo; assembly; long reads; PacBio; Oxford Nanopore; pile-o-gram; partial order alignment; force directed layout; vectorization
• Keywords (croatian): de novo; sastavljanje; dugačka očitanja; PacBio; Oxford Nanopore; gomila preklapanja; razmještaj simulacijom djelovanja sila; poravnanje parcijalnog uređaja; vektorizacija
• Language: english
• URN:NBN: urn:nbn:hr:168:043873
• Study programme: Title: Electrical Engineering and Computing; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti elektrotehnike i računarstva (Doktor znanosti elektrotehnike i računarstva)
• Type of resource: Text
• Extent: 83 str. ; 30 cm
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-29 13:03:08