Programska podrška za usporedba genoma eukariota

završni rad

• Naslov (engleski): Software for Comparing Eukaryotic Genomes
• Autor: Toni Sente
• Mentor: Mirjana Domazet-Lošo (mentor)
• Član povjerenstva: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Član povjerenstva: Damir Kalpić (član povjerenstva)
• Član povjerenstva: Igor Mekterović (č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: 2017-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U radu je ukratko opisan problem usporedbe i poravnanja dva genoma te je predložen efikasan algoritamski postupak za usporedbu i poravnanje koje koristi napredne strukture za indeksiranje teksta poput sufiksnog polja te Burrows-Wheelerove transformacije i tehniku dinamičkog programiranja za optimalno stvaranje niza najduljeg rastućeg podniza te lokalno poravnanje dijelova genoma korištenjem Smith-Waterman algoritma. Pri tome je detaljnije opisan svaki korak algoritma te vremenska i memorijska složenost kako pojedinog dijela algoritma, tako i cjelokupne implementacije. Konkretna implementacija programa izvedena je korištenjem programskog jezika Python 3, te je program uspoređen sa već postojećim programskim rješenjima.

Sažetak (engleski)

In this paper we briefly describe the problem of genome comparison and genome alignment. We suggest an efficient algorithm that uses advanced data structures such as suffix array and the Burrows-Wheeler transform and by using the dynamic programming technique we compute the longest common prefix and the local genome alignment with the Smith-Waterman algorithm. We also analyse the time and memory complexity of the program. Program was implemented with the Python 3 programming language. We also compare the suggested algorithm with already existing software.

• Ključne riječi: Usporedba genoma; MUMer
• Ključne riječi (engleski): Genome alignment; MUMer
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:199343
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-14 00:38:26