量子遺傳算法及其在多序列比對問題中的應(yīng)用.pdf

1、生物信息中的多序列比對問題，是建立系統(tǒng)發(fā)育樹，基因和蛋白質(zhì)的功能預(yù)測，探測序列之間的相互作用等的基礎(chǔ)。但是，多序列比對問題是一個(gè)NP—hard問題，非常具有挑戰(zhàn)性，對序列比對算法的速度和質(zhì)量有較高要求。 一些智能優(yōu)化方法應(yīng)用于該領(lǐng)域中，取得了不錯(cuò)的結(jié)果。遺傳算法是一種隨機(jī)迭代優(yōu)化算法，對于解決復(fù)雜的組合優(yōu)化問題有優(yōu)勢。但是由于多序列比對問題本身的復(fù)雜性，傳統(tǒng)的遺傳算法收斂速度比較慢，沒有指導(dǎo)的對個(gè)體進(jìn)行修正，帶有一定的盲目性，容

2、易產(chǎn)生退化現(xiàn)象。 在量子特性的啟發(fā)下，本文提出了一種新的量子遺傳算法QGAlign解決生物序列分析中的多序列比對問題。 算法首次提出了一種新的量子概率編碼方法，并設(shè)計(jì)了基于該編碼方法的量子旋轉(zhuǎn)角變異算子和五種遺傳算子。利用量子疊加態(tài)特性對染色體進(jìn)行編碼，增強(qiáng)了種群的多樣性；利用量子旋轉(zhuǎn)門通過最優(yōu)解來引導(dǎo)群體的進(jìn)化過程，加快了算法的收斂速度。為了避免量子旋轉(zhuǎn)門變異可能帶來局部最優(yōu)的問題，設(shè)計(jì)了基于多序列比對問題的遺傳算子，