多序列比對問題的粒子群優(yōu)化算法求解

《多序列比對問題的粒子群優(yōu)化算法求解》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、維普資訊http://www.cqvip.com多序列比對問題的粒子群優(yōu)化算法求解張鵬帥霍紅衛(wèi)(西安電子科技大學(xué)計算機(jī)學(xué)院，西安710071)E—mail：pshzhangCt~mail．xidian．edu．cn摘要文章提出了一新的算法，4'1用粒子群優(yōu)化算法求解多序列比對的問題，這是粒子群優(yōu)化算法在生物信息學(xué)方面的一個新的應(yīng)用。文章從粒子群算法的原理和多序列比對問題模型入手，來提出怎樣改造粒子群優(yōu)化算法使其可以解決多序列比對問題，最后給出利用粒子群優(yōu)化算法求解多序列比對的算法，及其測試結(jié)果。關(guān)鍵詞生物信息學(xué)雙序列比對多序列比對粒子群優(yōu)化算法文章編號1002-

2、8331-(2005)18-0084—04文獻(xiàn)標(biāo)識碼A中圖分類號TP301PSOforMultipleSequencesAlignmentZhangPengshuaiHuoHongwei(Schoo1ofComputerScience，XidianUniversity。Xian710071)Abatract：Thispaperintroducesanewalgorithm：theparticleswarmoptimization(PSO)forsolvingtheproblemofse—queneealignment．ItisanewattemptthatPSO

3、inthebioinformaticsappliedfield．Takethemuhiplesequencealignmentmodel，Analgorithmofakindofspecialparticleswarmoptimizationisconstructedanddon'tchanget}lecharaetersandadvantagesofPSO．Finally，ThepaperintroducestheMSAPSO(MultipleSequenceAlignmentPSO)andt}letestresuh．Keywords：bioinformati

4、cs，pairwisealignment，multiplesequencealigrmaent，particleswarmoptimisationl引言著眼于序列中的某些特殊片斷，比較這些片斷之間的相似性，在生物信息學(xué)中，對序列數(shù)據(jù)進(jìn)行相似性比較即序列比即局部比對(1ocalalignment)。對，是一種基本的信息處理方法，它對于發(fā)現(xiàn)生物序列中的功典型的雙序列比對算法是needleman—Wunsch算法[7／。雙能、結(jié)構(gòu)和進(jìn)化的信息具有非常重要的意義【11，而序列比對就是序列比對是序列分析的基礎(chǔ)。然而，對于構(gòu)成基因家族的成組運用某種特定的數(shù)學(xué)模型或算法，找出

5、兩個或多個序列之間最的序列來說，要建立多個序列之間的關(guān)系，這樣才能揭示整個大匹配堿基或殘基數(shù)，比對的結(jié)果反映了算法在多大程度上反基因家族的特征。這就要進(jìn)行多序列比對(Multiplesequence映了序列之間的相似性關(guān)系以及他們的生物學(xué)特征。alignment)由于可以提高序列比對的信噪比，多序列比對在闡序列比對的發(fā)展已經(jīng)有40對年的時間了，Gibbs于1970明一組相關(guān)序列的重要生物學(xué)模式方面起著相當(dāng)重要的作用。年提出了點陣法13]，1981年Smitll和waterman提出了動態(tài)規(guī)劃多序列比對是進(jìn)行生物序列分析的最基本的任務(wù)之一，它算法，應(yīng)用最廣的有Fa

6、sta[~和Blast算法婀。在發(fā)現(xiàn)序列模體(motif)和保守區(qū)域、系統(tǒng)發(fā)育分析、結(jié)構(gòu)預(yù)測當(dāng)今生物信息學(xué)領(lǐng)域的主要研究方向之一，是從研究蛋白等方面具有重要的作用，是生物信息學(xué)當(dāng)前的研究熱點問題之’一質(zhì)功能人手，進(jìn)而闡明進(jìn)化關(guān)系。以序列為基礎(chǔ)，用序列分析的O手段以及所得的結(jié)果推斷生物大分子的功能是其常用的方法已有的多序列比對算法有：Needlman—Wunsch算法、Car-之一?；境霭l(fā)點，是通過和數(shù)據(jù)庫中已知功能的序列進(jìn)行相rilo—LipmantSt"J~法、廣泛使用的多序列比對軟件包ClustalW~基似性比對，確定那些新測定的序列與已知序列之間的關(guān)系。

7、于漸進(jìn)比對思想構(gòu)建、SAGAt01基于遺傳算法構(gòu)建。確定DNA序列之間或蛋白質(zhì)序列之間相似性程度的過程該文研究一種新的序列比對的方法，利用粒子群優(yōu)化算法稱為序列比對(sequencealignment)?？梢酝ㄟ^插入空位得到更(PSO)來實現(xiàn)基因序列的比對。這是一個嶄新的嘗試。好的匹配。序列比對是序列分析和數(shù)據(jù)庫搜索的基礎(chǔ)，也可用來找出保守的序列模體。序列比對分為雙序列比對和多序列比2粒子群優(yōu)化算法(PSO)對。人類受到社會系統(tǒng)、物理系統(tǒng)、生物系統(tǒng)等運行機(jī)制啟發(fā)，雙序列比對(pairwisealignment)是指通過一定算法對兩建立和發(fā)展許多方法來解決實際的問

8、題。典型的有遺傳算法、個