Programska podrška za usporedba genoma eukariota

undergraduate thesis

• Title (english): Software for Comparing Eukaryotic Genomes
• Author: Toni Sente
• Mentor: Mirjana Domazet-Lošo (mentor)
• Committee member: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Committee member: Damir Kalpić (član povjerenstva)
• Committee member: Igor Mekterović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: Usporedba genoma; MUMer
• Keywords (english): Genome alignment; MUMer
• Language: croatian
• URN:NBN: urn:nbn:hr:168:199343
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-14 00:38:26