Poravnanje genoma korištenjem skrivenog Markovljevog modela

završni rad

• Naslov (engleski): Genome alignment based on hidden Markov model
• Autor: Jurica Kuleš
• Mentor: Mirjana Domazet-Lošo (mentor)
• Član povjerenstva: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Član povjerenstva: Ivica Botički (član povjerenstva)
• Član povjerenstva: Tomislav Jagušt (č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: 2022-09-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: bioinformatika; genomika; poravnanje genome; skriveni Markovljevi modeli; Needleman-Wunschov algoritam
• Ključne riječi (engleski): bioinformatics; genomics; genome alignment; hidden Markov models; Needleman-Wunsch algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:134344
• 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: 2023-01-15 10:38:35