Računalne metode za poboljšanje i validaciju sastavljenih genoma

diplomski rad

• Naslov (engleski): Computational approaches for refinement and validation of genome assemblies
• Autor: Vanessa Županović
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Mladen Vučić (član povjerenstva)
• Član povjerenstva: Damir Seršić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2014-07-07, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Sekvenciranje jest postupak kojim se unutar odred¯ene sekvence utvrd¯uje tocˇan redoslijed
pojedinih baza. Kako genome nije mogu´ce sekvencirati u cijelosti služimo
se razliˇcitim raˇcunalnim postupcima (algoritmima) kako bi rekonstruirali (sastavili)
polazni genom. Zadnji korak u sastavljanju genoma predstavlja skafolding koji se u
osnovi može svesti na problem utvrd¯ivanja orijentacije te redoslijeda vec´ prethodno
djelomiˇcno sastavljenih sekvenci - kontiga, tj. pokušavamo smjestiti kontige u kontekst
ˇcitavog genoma, naravno, trenutno ne postoje metode koje bi to uˇcinile sa sto
postotnom toˇcnoš´cu, stoga unutar ovoga rada razvijamo više heuristiˇckih postupaka
koji bi trebali smanjiti broj pogrešaka pri sastavljanju. Svi razvijeni postupci zasnivaju
se na ˇcinjenici da je katkad vrlo teško jednoznaˇcno odrediti toˇcnu poziciju malog kontiga
unutar genoma, stoga ga se može smjestiti na više pozicija u genomu bez da se
naruši ijedan od uvjeta na bridove skafold grafa. Dakle, ono što ˇcinimo u svakom od
razvijenih postupaka jest: detekcija višeznaˇcnih regija i uklanjanje nejednoznaˇcnosti
micanjem kontiga koji uzrokuje nejednoznaˇcnost u zaseban skafold. Naravno, prilikom
micanja kontiga na njegovoj prvotnoj poziciji stvaramo procjep, stoga je važno
da na kraju procesiranja provjerimo je li mogu´ce ponovno popuniti procjepe nastale
kao posljedica istog. Implementirane metode validirane su cjevovodom GAGE, a rezultati
validacije pokazali su se kao vrlo obe´cavaju´ci , zbog ˇcega ´ce metode zasigurno
poslužiti kao osnova za neka budu´ca istraživanje te potencijalna poboljšanja.

Sažetak (engleski)

Sequencing is the process of determining the right order of nucleotides within the
DNA molecule. However, we can not sequence the entire genome of certain organism
at once, so we are forced to use different computational approaches (genome assembly
methods) in order to reconstruct the initial sequence from the large amount of relatively
small sequencing fragments. The last step in genome assembly is called scaffolding.
Scaffolding can be visualized as the problem of ordering and orienting contigs and it
is a crucial step in the assembly of high-quality draft genomes. Currently, there are no
scaffolding methods that can produce 100% accurate scaffolds, so in this work we are
introducing different heuristic algorithms which can significantly reduce the number of
errors inside the existing scaffolds. All of our approaches are based on the fact that sometimes
it is really difficult to correctly place small contigs inside genome which leads
us to the problem od ambiguous order that we are trying to slove by detecting ambiguous
regions inside scaffolds and removing contigs that are causing the ambiguity.
After the removing wrongly scaffolded contigs, we must check if the gap (which was
caused by contig removal) can be filled. The developed methods were evaluated using
the GAGE pipeline. The results of evaluation seemed to be very promising which led
as to the conclusion that our methods would make a good start for some future research
and development of other similar approaches.

• Ključne riječi: GAGE; OPERA; sastavljanje genoma; sekvenciranje; skafolding; skafold graf
• Ključne riječi (engleski): GAGE; OPERA; genome assembly; genome sequencing; scaffolding; scaffold graph
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:613858
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 14:38:49