Približni algoritam za brzo računanje poravnanja dvaju dugačkih nizova

undergraduate thesis

• Title (english): Approximate Algorithm for Computing Alignment Between Two Long Sequences
• Author: Filip Sodić
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (predsjednik povjerenstva)
• Committee member: Krešimir Križanović (član povjerenstva)
• Committee member: Robert Vaser (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2018-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Globalno poravnanje genoma važan je problem genomike. Zbog duljine genoma, računanje optimalnog puta poravnanja točnim algoritmima dinamičkog programiranja računalno je neizvedivo. Cilj ovog rada predstavljanje je i implementacija heurističkog algoritma poravnanja temeljenog na tehnikama traženja predstavnika i procjene Jaccardovog koeficijenta sličnosti skiciranjem.

U poglavlju 2 dan je popis pretpostavki neophodnih za rad algoritma te popis pojmova za pomoć pri njegovom razumijevanju. Poglavlje 3 iznosi formalnu definiciju problema, a konkretan algoritam razvijen za njegovo rješavanje opisan je poglavljem 4. Implementacijski specifični detalji nevažni za opis algoritma na visokoj razini navedeni su u poglavlju \5. Rezultati i učinkovitost implementiranog algoritma istraženi su u poglavlju 6. Konačno, poglavlje 7 ukratko izdvaja najbitnije ideje rada.

Abstract (english)

Global sequence alignment is an important problem in the field of genomics. At the whole genome scale, computing the optimal alignment path by using an exact dynamic programming algorithm is computationally impossible. This paper looks to present and implement a heuristic alignment algorithm which relies on computing sequence minimizers and sketch-based estimations of the Jaccard index.

The assumptions and preliminaries necessary to understand the algorithm are given by chapter 2. Chapter 3 formally defines the studied problem, while chapter 4 presents and explains the proposed solution. Implementation details not directly connected to the algorithm itself are listed in chapter 5. Performance and results yielded by the implementation are explored in chapter 6. Chapter 7 provides a quick overview of the main ideas presented throughout the paper.

• Keywords: MinHash; Jaccard; Winnowing; Predstavnik; Skiciranje; Poravnanja dugih očitanja
• Keywords (english): MinHash; Jaccard; Winnowing; Minimizer; Sketching; long read mapping
• Language: croatian
• URN:NBN: urn:nbn:hr:168:487992
• 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:49:31