DNA sequencing based on Euler path with improved Hierholzer algorithm

magistrsko delo

Filip Mesarić (Avtor), Domen Mongus (Mentor)

Povzetek

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.

Ključne besede

DNA;Eulerian path;Hierholzer's algorithm;DNA sequencing;magistrske naloge;

Podatki

Jezik:	Angleški jezik
Leto izida:	2019
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	F. Mesarić
UDK:	004.421(043.2)
COBISS:	22512406
Št. ogledov:	771
Št. prenosov:	96
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	DNA sequencing based on Euler path with improved Hierholzer algorithm
Sekundarni povzetek:	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.
Sekundarne ključne besede:	DNK;Eulerjeva pot;Hierhozerov algoritam;sekvenca 4;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Strani:	IX, 38 str.
ID:	11185905