Aplikacija za mapiranje očitanja na referencu s optimizacijom potrošnje memorije

završni rad

• Naslov (engleski): Application for Mapping Reads to a Reference With Optimized Memory Usage
• Autor: Fran Mička
• Mentor: Krešimir Križanović (mentor)
• Član povjerenstva: Krešimir Križanović (predsjednik povjerenstva)
• Član povjerenstva: Filip Bosnić (član povjerenstva)
• Član povjerenstva: Josipa Lipovac (č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-08-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu opisan je postupak poravnanja sekvenci na referentni genom. Svaki korak postupka obilježen je jednim od algoritama koji su definirani u poglavljima rada. Početak rada prikazuje i objašnjava algoritam pronalaženja minimizera u nizu, te njihovu potrebu za daljnje poravnanje. Nadalje, uvodi se pojam poravnanja nizova i definiraju se dinamički algoritmi za izračun poravnanja: Needleman-Wunsch, Smith-Waterman, polu-globalni, te Hirschbergov algoritam. Na kraju rada opisan je postupak traženja najduljeg rastućeg podniza, te spajanja svih ranije navedenih algoritama u cjeloviti program. Uz to provedena je i usporedba rezultata ovog programa sa rezultatima minimapa2.

Sažetak (engleski)

In this paper, the sequence alignment procedure on the reference genome is described. Each step of the procedure is marked by one of the aglorithms defined in the chapters of the paper. Beginning of the paper shows and explains the algorithm for finding minimizers in a sequence. Furthermore, the notion of sequence alignment is introduced and dynamic algorithms for calculating alignment are defined: Needleman-Wunsch, Smith-Waterman, semi-global, and Hirschberg algorithm. At the end of the paper, the procedure of searching for the longest increasing subsequence, and merging of all the previously mentioned algorithms into a complete program is described. In addition, a comparison of the results of this program with the results of the minimap2 was conducted.

• Ključne riječi: minimizeri; poravnanje nizova; dinamičko programiranje; najdulji rastući podniz
• Ključne riječi (engleski): minimizers; sequence alignment; dynamic programming; longest increasing subsequence
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:541703
• 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:50:29