资源描述：
《基于剖面隐马氏模型的多序列比对》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第29卷第4期食品与生物技术学报Vol.29No.42010年7月JournalofFoodScienceandBiotechnologyJul.2010文章编号:16731689(2010)04063407基于剖面隐马氏模型的多序列比对121*1李成渊,龙海侠,孙俊,须文波(1.江南大学信息工程学院,江苏无锡214122;2.江南大学教育学院,江苏无锡214122)摘要:多序列比对被称为NP完全问题,是生物信息中最基本的问题之一。目前,广泛使用剖面隐马尔可夫模型解决多序列比对问题。作者在粒子群优化算法的基础上,提出了将量子粒子群
2、优化算法用于剖面隐马尔可夫模型的训练过程,进而构建了一种基于剖面隐马氏模型和量子粒子群优化算法的多序列比对算法。从核酸序列和BaliBASE比对数据库中选取了一些比对例子进行了模拟实验,并与其他算法进行了比较,结果表明,所提出的算法能在有限的时间内不仅能找到理想的隐隐马尔可夫模型,而且能得到最优的比对结果。关键词:多序列比对;剖面隐马尔可夫模型;量子粒子群优化算法中图分类号:Q811.4文献标识码:AMultipleSequenceAlignmentBasedOntheProfileHiddenMarkovModel121*1LIChengyuan,LONGHaixia,
3、SUNJun,XUWenbo(1.SchoolofInformationTechnology,JiangnanUniversity,Wuxi214122,China;2.SchoolofEducation,JiangnanUniversity,Wuxi214122,China)Abstract:Multiplesequencealignment(MSA),knownasNPcompleteproblem,isoneofthebasicproblemsincomputationalbiology.AtpresentProfileHiddenMarkovModel(HMM)w
4、aswidelyusedinmultiplesequencealignment.Thismanuscriptpresentedthequantumbehavedparticleswarmoptimization(QPSO)whichwasbasedonparticleswarmoptimization.TheproposedalgorithmwasusedtooptimizetheprofileHMM.Furthermore,anintegrationalgorithmbasedontheprofileHMMandQPSOfortheMSAwasconstructed.Then
5、theapproachwasevaluatedbyasetofstandardinstanceswhicharechosenfromnucleotidessequencesandthebenchmarkalignmentdatabase,nameasBAliBASE.Finallyourresultsarecomparedwithotheralgorithms.TheresultshownthattheproposedalgorithmnotonlyfindsouttheperfectprofileHMM,butalsoobtainstheoptimalalignmentofmu
6、ltiplesequence.Keywords:multiplesequencealignment,profilehiddenmarkovmodel,quantumbehavedparticleswarmoptimization核苷酸或氨基酸的多序列比对或联配是生物信息学中最重要、最具有挑战性的任务之一。多序收稿日期:20090807作者简介:李成渊(1980-),男,江苏无锡人,生物信息学博士研究生。Email:lichengyuaning@gmail.com*通信作者:须文波(1946-),男,江苏无锡人,教授,博士生导师,主要从事生物信息学方面的研究。Emai
7、l:xwb_sytu@hotmail.com第4期李成渊等:基于剖面隐马氏模型的多序列比对635列比对问题是一个将不等长的多个序列通过插入为了克服BaumWelch算法和PSO算法的缺[9-10]空位变成等长的过程,这些位置上的空位代表着相点,我们使用量子粒子群优化算法(QPSO)来比对的序列从共同的祖先通过插入/删除操作的进训练隐马尔可夫模型,不仅参数个数少,随机性强,化过程。利用多序列比对算法得到的最优比对,可并且能覆盖所有解空间,保证算法的全局收敛。用于找出蛋白质家族的
