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

završni rad

• Naslov (engleski): Approximate Algorithm for Computing Alignment Between Two Long Sequences
• Autor: Filip Sodić
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Krešimir Križanović (član povjerenstva)
• Član povjerenstva: Robert Vaser (č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: 2018-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: MinHash; Jaccard; Winnowing; Predstavnik; Skiciranje; Poravnanja dugih očitanja
• Ključne riječi (engleski): MinHash; Jaccard; Winnowing; Minimizer; Sketching; long read mapping
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:487992
• 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: 2019-03-14 00:49:31