Poravnanje genoma korištenjem skrivenog Markovljevog modela

undergraduate thesis

• Title (english): Genome alignment based on hidden Markov model
• Author: Jurica Kuleš
• Mentor: Mirjana Domazet-Lošo (mentor)
• Committee member: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Committee member: Ivica Botički (član povjerenstva)
• Committee member: Tomislav Jagušt (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-09-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U zadnjih nekoliko desetljeća, došlo je do značajnih pomaka u području genomike, ponajviše zahvaljujući bioinformatičkoj analizi, čiji je najčešći početni korak poravnanje genoma. U ovom radu naveo sam osnovne biološke pojmove iz područja genomike, predstavio osnovne mjere udaljenosti između bioloških sljedova te opisao Needleman-Wunschov algoritam za dobivanje optimalnog poravnanja dvaju sljedova. Najveći fokus bio je na matematičkom konceptu skrivenog Markovljevog modela i njegovoj primjeni na poravnanje dvaju genoma. Nadalje, predstavio sam tri glavna problema kod skrivenih Markovljevih modela i razradio njihova klasična rješenja. Opisao sam postupak procjene parametara modela, postupak izračuna optimalnog poravnanja korištenjem programskog jezika Python i biblioteke NumPy te proveo evaluaciju tako dobivenih rješenja. Također sam napravio analizu vremenske složenosti modela, ovisno o različitim veličinama ulaznog skupa podataka.

Abstract (english)

In the last few decades, there have been significant advances in the field of genomics, mostly thanks to bioinformatic analysis, whose most common initial step is genome alignment. In this paper I presented basic biological concepts in the field of genomics, basic measures of distance between biological sequences and described the Needleman-Wunsch algorithm for obtaining optimal alignment of two sequences. The main focus was on the mathematical concept of the hidden Markov model and its application to the alignment of two genomes. Furthermore, I laid down the three fundamental problems with hidden Markov models and elaborated their classical solutions. I described the procedure of estimating the model parameters and the procedure of calculating the optimal alignment using the Python programming language alongside the NumPy library and performed an evaluation of the solutions obtained in this way. I also made an analysis of the time complexity depending on the different sizes of the input data set of the model.

• Keywords: bioinformatika; genomika; poravnanje genome; skriveni Markovljevi modeli; Needleman-Wunschov algoritam
• Keywords (english): bioinformatics; genomics; genome alignment; hidden Markov models; Needleman-Wunsch algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:134344
• 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: 2023-01-15 10:38:35