Algorithms for de novo genome assembly from third generation sequencing data : doctoral thesis - Sović, Ivan; Šikić, Mile; Skala, Karolj (Zagreb : I. Sović ; Fakultet elektrotehnike i računarstva, 2016)
ijekom 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.

U okviru ove disertacije, razvijene su četiri nove metode: (I) NanoMark - sustav za automatiziranu usporedbu i evaluaciju metoda za sastavljanje ONT podataka; (II) GraphMap - brza i osjetljiva metoda za mapiranje dugačkih i greškovitih očitanja; (III) Owler - osjetljiva metoda za preklapanje očitanja dobivenih sekvenciranjem treće generacije; i (IV) Racon - iznimno brza konsenzus metoda za ispravljanje greškovitih dugačkih sekvenci nakon što je proveden postupak sastavljanja. Owler i Racon korišteni su kao osnovni moduli za razvoj nove metode za de novo sastavljanje genoma nazvane Aracon. Rezultati testiranja pokazuju kako je Aracon smanjio sveukupno potrebno vrijeme sastavljanja genoma za faktor izmed̄u 3x − 10x u usporedbi s trenutno vodećim dostupnim metodama, pri čemu mu je kvaliteta sastavljenih genoma jednaka ili bolja od istih metoda.
Ključne riječi: de novo, sastavljanje, PacBio, nanopore, NanoMark, GraphMap, Racon, Aracon
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.

In the scope of this thesis, four new methods were developed: (I) NanoMark - an evaluation framework for comparison of assembly methods from nanopore sequencing data; (II) GraphMap - a fast and sensitive mapper for long error-prone reads; (III) Owler - a sensitive overlapper for third generation sequencing; and (IV) Racon - a rapid consensus module for cor- recting raw assemblies. Owler and Racon were used as modules in the development of a novel de novo genome assembler Aracon. The results show that Aracon reduces the overall assembly time by at least 3x and up to even an order of magnitude less compared to the state-of-the-art methods, while retaining comparable or better quality of assembly.
Keywords: de novo, assembly, PacBio, nanopore, NanoMark, GraphMap, Racon, Aracon
Bibliografija str. 137-152.