Computational approaches for refinement and validation of genome assemblies

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.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