20.500.12556/DKUM-73363 Določanje sekvence DNK na osnovi Eulerjeve poti z uporabo izboljšanega Hierholzerjevega algoritma magistrsko delo DNA sequencing based on Euler path with improved Hierholzer algorithm In the master’s thesis we created the algorithm for DNA sequencing based on an Eulerian path and the improved Hierholzer’s algorithm. The theoretical part explains the graph theory, existing Eulerian path searching algorithms and Hierholzer's algorithmic implementations. Additionally, the theoretical part presents DNA sequencing and its most popular methods. The practical part focuses on the development of an application that shows DNA sequencing based on an Eulerian path and the improved Hierholzer's algorithm. The results represent an improvement of sequencing, taking into consideration time and distance measurements, for our implementation in comparison with the existing Hierholzer’s algorithm. 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. DNA Eulerian path Hierholzer’s algorithm DNA sequencing DNK Eulerjeva pot Hierhozerov algoritam sekvenca 4 true true false F. Mesarić Angleški jezik Slovenski jezik Magistrsko delo/naloga 2019-03-29 14:39:20 2019-07-15 12:16:21 2022-08-02 00:38:26 2019-08-09 03:14:18 2019 0 Maribor 0 Maribor IX, 38 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.421(043.2) 22512406 URN:SI:UM:DK:XEUXZVPT MAG_Mesaric_Filip_2019.pdf MAG_Mesaric_Filip_2019.pdf 1 B7DD6AAB89940D4DC0A350C4BFEB1CE8 126e0e876eee181b30516c0d4a6cd7fe68cefe697484a2126e592be9c1bc3890 7d9f7036-7c07-11eb-bb7a-00155d0001ca 20.500.12556/dkum/c74f1749-66bb-4b21-95d7-a13011bf0e49 https://dk.um.si/Dokument.php?lang=slv&id=135285 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0