基于競(jìng)爭(zhēng)策略的多序列比對(duì)算法.pdf

1、在分子生物學(xué)和基因組分析中,蛋白質(zhì)序列和DNA序列的比對(duì)是一種重要的分析工具.多序列比對(duì)問題是NP完全問題,這就是說,任何研究快而完全算法的企圖都將面臨極大困難.求解多序列比對(duì)問題可以看成是在一個(gè)有向無環(huán)圖中尋找兩點(diǎn)間的最短路徑,求解此類問題眾所周知的方法是動(dòng)態(tài)規(guī)劃方法,但是使用動(dòng)態(tài)規(guī)劃方法得到最優(yōu)比對(duì)需要消耗大量的時(shí)間和空間,對(duì)于規(guī)模較大的情形,原封不動(dòng)地照搬動(dòng)態(tài)規(guī)劃方法求解從現(xiàn)實(shí)角度是不可能的. 首先,提出了一種稱之為基于競(jìng)爭(zhēng)策略的

2、快速多序列比對(duì)近似算法,多序列比對(duì)算法分為同時(shí)比對(duì)算法和非同時(shí)比對(duì)算法,該算法為一同時(shí)比對(duì)算法.使用該算法對(duì)基因庫Balibase2.01中的序列簇進(jìn)行了測(cè)試,并將實(shí)驗(yàn)結(jié)果與著名的同時(shí)比對(duì)算法MSA進(jìn)行了比較,實(shí)驗(yàn)結(jié)果表明該算法是一種十分高效的同時(shí)比對(duì)算法. 其次,在基于競(jìng)爭(zhēng)策略的多序列比對(duì)算法的基礎(chǔ)上采用分治策略對(duì)比對(duì)結(jié)果進(jìn)行了進(jìn)一步的處理,也就是進(jìn)行優(yōu)化.采用了一定的方法將原問題轉(zhuǎn)化成了幾個(gè)子問題,然后對(duì)每個(gè)子問題采用原算法進(jìn)行求解