Algoritam za određivanje ukupnog poravnanja dva grafa poravnanja parcijalnog uređaja

završni rad

• Naslov (engleski): Algorithm for the Alignement of Two Partial Order Alignment Graphs
• Autor: Mislav Bradač
• 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: 2017-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Poravnanja više slijedova je jedan od temeljnih problema bioinformatike. Za
analitično poravnanje dva slijeda već se desecima godina koristi
Smith-Waterman obitelj algoritama, no zbog svoje velike prostorne i vremenske
složenosti ti algoritmi nisu pogodni za poravnanje većeg broja slijedova. Kao prvi
korak poravnanja većeg broja slijedova izgrađuje se graf poravnanja parcijalnog
uređaja koristeći modificirani Smith-Waterman algoritam. Tako izgrađen graf
pogodan je za daljnu analizu slijedova: generiranje poravnanja većeg broja
slijedova te pronalaženja konsenzusa. U ovom radu predstavljen je algoritam za
spajanje dva već postojeća grafa poravnanja parcijalnog uređenja koji zbog
korištenja već izgrađenog grafa smanjuje broj koraka potrebnih za igradnju
većeg grafa.

Sažetak (engleski)

Sequence alignment is one of fundemental problems in bionformatics. Alignment of
two sequences is done using Smith-Waterman family of algorithms. These algorithms
are not useable for alignment of multiple sequences because of theirs big time
and memory complexity. Partial order alignment (POA) graph is a first step of
calculating multiple sequence alignment efficiently. POA graph is suitable for
further analysis of sequences: calculation of multiple sequence alignment and
concensus generation. In this thesis algorithm for merging two already existing
POA graph is presented. Algorithm reduces number of steps needed to build
bigger POA graphs by reusing parts of existing ones.

• Ključne riječi: bioinformatika; POA; graf poravnanja parcijalnog uređaja; konsenzus; Smith-Waterman; poravnanje slijedova
• Ključne riječi (engleski): bioinformatics; POA; partial order alignment graph; concensus; Smith-Waterman; sequence alignment
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:809403
• 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-13 19:16:08