Naslov
Algoritam za određivanje ukupnog poravnanja dva grafa poravnanja parcijalnog uređaja
(Algorithm for the Alignment of Two Partial Order Alignment Graphs)

Autori
Bradač, Mislav

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet Elektrotehnike i Računarstva

Mjesto
Zagreb

Datum
04.07

Godina
2017

Stranica
27

Mentor
Šikić, Mile

Ključne riječi
bioinformatika, PAO, graf poravnanja parcijalnog uređaja, koncenzus, Smith-Waterman, poravnanje slijedova
(bioinformatics, POA, partial order alignment graph, concensus, Smith-Waterman, sequence alignment)

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 koncenzusa. 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.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA