| Abstract: | Magistrsko delo obravnava temo sekvenciranja DNK na podlagi Eulerove poti z uporabo
izboljšanega Hierholzerjevega algoritma. Delo temelji predvsem na sekvenciranju DNK, ki
določa gensko zaporedje in je pomembno za razumevanje živih organizmov. Različni
eksperimenti se izvajajo nad fragmenti DNA, na podlagi katerih so narejeni grafi s katerimi se
rešuje problem sestavljanja genoma. Cilj dela je razvoj aplikacije, ki omogoča sekvenciranje
DNK z uporabo izboljšanega Hierhaloidovega algoritma. Rezultati so evalvirani s časovno
analizo. Ustvarjanje aplikacije poskuša odgovoriti, ali se teorija grafov lahko uporablja za
izboljšanje sekvenciranja DNK, tudi kako Hierholzerjev algoritem vpliva na sekvenciranje DNK
in kakšno vlogo ima Eulerjeva pot. Namen magistrske naloge je najti boljšo metodo
sekvenciranja DNK, ki temelji na teoriji grafov.
V teoretičnem delu je razložena relativno nova veja matematike – teorija grafov, definirani je
preprosti graf in možnosti njegove uporabe. Predstavljena je njihova uporabnost v primeru
sekvenciranja DNA vključno z Eulerjevo poti. Znotraj teoriji grafov so predstavljeni notranji in
zunanji stopnji grafa skupaj s balansiranem usmerjenem grafom. Razložen je primer
preprostega grafa z dvema različnima tipoma predstavitve: matriko sosedov in matriko
pojavnosti. V nadaljevanju teoretičnega dela je predstavljena razlaga Hierholzeroega in
izboljšanega Hierholzerov algoritma, ter njegova algoritemska izvedba. Razložen je De
Bruijnov graf, ki se uporablja kot osnova sekvenciranja v enim izmed treh izbranih referenčnih
raziskovanj. Trije referenčni znanstveni članki predstavljajo različne algoritme za DNK
sekvenciranje. Poudarek je na predstavitvi metod sekvenciranja DNK in možnosti uporabe
VI
Eulerjeve poti v sekvenciranju. Opredeljene so DNK podrobnosti skupaj z različnimi metodami
sekvenciranja, vključno s šestimi: Maxam – Gilbert sekvenciranje, Chain - termination metoda,
Dye - termination sekvenciranje, Automation and simple preparation, Large-scale strategije
sekvenciranja in nove metode sekvenciranja.
Praktični del naloge opisuje razvoj aplikacije za sekvenciranje DNA. Pridobljeni rezultati so
dolžina DNK, Hammingova in Edit razdalja in čas izvršitve. Hammingova razdalja se nanaša na
število točk, pri katerih se razlikujeta dva različna podatka. Podobno, Edit razdalja izračuna
najmanjše število zahtevanih izmenjav med dva različna podatka. Za namen izdelave aplikacije
je pomembno vnaprej določiti verigo DNA, iz katere se izdela začetni graf z označenimi
vozlišči. Po poteku več korakov se poda Eulerjeva pot iz prvotno definiranega grafa in se
prikaže končna veriga DNA. Algoritem se izvajal v okviru pet testi. Pri vsakem preskusu je bila
kot parameter vzeta dolžina DNK. Zanesljivost rezultatov se dosegla s 100-kratnim izvajanjem
algoritma. Iz 100 iteracij se izračunala povprečna vrednost časa izvajanja. Rezultati vseh
opravljenih testov so se analizirali in prikazali na grafikoni. Lastna implementacija, izdelana na
podlagi izboljšanega Hierholzerovega algoritma, se pokazala kot najhitrejša. Tako da se lahko
sklepa, da obstaja možnost skrajševanja časa sekveciranja s uporabo implementiranega
algoritma. Delo se lahko nadaljuje tudi z dodatnimi testi in poenostavitvijo grafov ter z
uporabo drugačne vrste algoritmov. |
|---|
