hrvatski

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

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.

bioinformatika, PAO, graf poravnanja parcijalnog uređaja, koncenzus, Smith-Waterman, poravnanje slijedova

nije evidentirano