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

undergraduate thesis

• Title (english): Application for Mapping Reads to a Reference With Optimized Memory Usage
• Author: Fran Mička
• Mentor: Krešimir Križanović (mentor)
• Committee member: Krešimir Križanović (predsjednik povjerenstva)
• Committee member: Filip Bosnić (član povjerenstva)
• Committee member: Josipa Lipovac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-08-29, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

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