Algorithms for de novo genome assembly from third generation sequencing data

doctoral thesis

• Title (croatian): Algoritmi za de novo sastavljanje genoma iz sekvenciranih podataka treče generacije
• Author: Ivan Sović
• Mentor: Mile Šikić (mentor)
• Mentor: Karolj Skala (komentor)
• 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: 2016, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing; Data Processing
• Universal decimal classification (UDC): 621.3 - Electrical engineering

Abstract

During the past ten years, genome sequencing has been an extremely hot and active topic, with an especial momentum happening right now. New, exciting and more affordable technologies have been released, requiring the rapid development of new algorithmic methods to cope with the data. Affordable commercial availability of the sequencing technology and algorithmic methods which can leverage the data could open doors to a vast number of very important applications, such as diagnosis and treatment of chronic diseases through personalized medicine or identification of pathogenic microorganisms from soil, water, food or tissue samples. Sequencing the entire genome of an organism is a difficult problem, because all sequencing technologies to date have limitations on the length of the molecule that they can read (much smaller than the genomes of a vast majority of organisms). In order to obtain the sequence of an entire genome, reads need to be either stitched together (assembled) in a de novo fashion when the genome of the organism is unknown in advance, or mapped and aligned to the reference genome if one exists (reference assembly or mapping). The main problem in both approaches stems from the repeating regions in the genomes which, if longer than the reads, prevent complete assembly of the genome. The need for technologies that would produce longer reads which could solve the problem of repeating regions has resulted in the advent of new sequencing approaches – the so-called third generation sequencing technologies which currently include two representatives: Pacific Biosciences (PacBio) and Oxford Nanopore. Both technologies are characterized, aside from long reads, by high error rates which existing assembly algorithms of the time were not capable of handling. This caused the development of time-consuming read error correction methods which were applied as a pre-processing step prior to assembly. Instead, the focus of the work conducted in the scope of this thesis is to develop novel methods for de novo DNA assembly from third generation sequencing data, which provide enough sensitivity and precision to completely omit the error-correction phase. Strong focus is put on nanopore data.

Abstract (croatian)

Tijekom proteklih desetak godina, sekvenciranje genoma postalo je iznimno aktivno i zanimljivo područje, a pravi zamah dogad̄a se upravo sada. Nedavno su se počele pojavljivati nove, uzbudljive i pristupačne tehnologije, koje povlače i potrebu za razvojem novih algoritamskih metoda koje će se moći uhvatiti u koštac s količinom i kvalitetom podataka koje one generiraju. Komercijalna isplativost i dostupnost tehnologije za sekvenciranje, kao i pratećih algoritamskih rješenja kojima bi se maksimizirao potencijal ovih tehnologija, mogao bi otvoriti vrata širokom spektru važnih primjena: od dijagnoze i tretmana kroničnih bolesti kroz personaliziranu medicinu, pa do identifikacije patogenih mikroorganizama iz uzoraka tla, vode ili tkiva. Sekvenciranje cijelog genoma nekog organizma predstavlja vrlo složen problem jer sva postojeća tehnologija za sekvenciranje sadrži jedno važno ograničenje - najveću duljinu molekule koju ured̄aji mogu pročitati. Duljine očitanih sekvenci (očitanja) puno su kraća od duljine genoma velike većine organizama. Kako bi se uspješno mogla dobiti cjelovita sekvenca nekog genoma, očitanja je potrebno med̄usobno povezati (sastaviti) na de novo način u slučaju kada genom promatranog organizma već nije poznat unaprijed, ili ih je potrebno mapirati i poravnati s referentnim genomom promatranog organizma, u slučaju ako referentni genom već postoji (sastavljanje uz referencu ili mapiranje). U oba slučaja, osnovni problem javlja se u ponavljajućim regijama u genomu, koje, ako su duže od samih očitanja, onemogućuju jednoznačnu i potpunu rekonstrukciju genoma. Potreba za tehnologijama koje bi mogle prevladati problem ponavljajućih regija rezultirala je pojavom nove, treće generacije ured̄aja za sekvenciranje. Treća generacija trenutno uključuje samo dva reprezentativna proizvod̄ača ured̄aja: Pacific Biosciences (PacBio) i Oxford Nanopore Technologies (ONT). Osim dugačkih očitanja, obje tehnologije karakterizira i jako visoka razina pogreške u izlaznim podatcima. Razina pogreške dovoljno je velika da je postojeći algoritmi za sastavljanje genoma ne mogu uspješno prevladati. To je potaknulo razvoj vremenski vrlo zahtjevnih statističkih metoda za popravljanje podataka i smanjivanje pogreške kako bi se postojeće metode za sastavljanje mogle uspješno primijeniti. Umjesto ovako opisanog pristupa, cilj rada napravljenog u sklopu ove disertacije bio je razviti nove metode i algoritme za de novo sastavljanje DNA iz sekvenciranih podataka treće generacije koji imaju jako visoku osjetljivost i preciznost, čime bi se omogućilo potpuno preskakanje potrebe za ispravljanjem podataka. Pri tome, snažan fokus tijekom istraživanja stavljen je na ONT podatke.

• Keywords: de novo; assembly; PacBio; nanopore; NanoMark; GraphMap; Racon; Aracon
• Keywords (croatian): de novo; sastavljanje; PacBio; nanopore; NanoMark; GraphMap; Racon; Aracon
• Language: english
• URN:NBN: urn:nbn:hr:168:489121
• 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: 157 str. ; 30 cm.
• File origin: Born digital
• Access conditions: Closed access
• Repository: FER Repository
• Created on: 2019-04-11 12:24:21