Algorithm for the Alignement of Two Partial Order Alignment Graphs

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