李成渊, 龙海侠, 孙俊, 须文波＊

(1.江南大学信息工程学院,江苏无锡 214122;2.江南大学教育学院,江苏无锡 214122)

基于剖面隐马氏模型的多序列比对

李成渊1, 龙海侠2, 孙俊1, 须文波＊1

(1.江南大学信息工程学院,江苏无锡 214122;2.江南大学教育学院,江苏无锡 214122)

多序列比对被称为NP完全问题,是生物信息中最基本的问题之一。目前,广泛使用剖面隐马尔可夫模型解决多序列比对问题。作者在粒子群优化算法的基础上,提出了将量子粒子群优化算法用于剖面隐马尔可夫模型的训练过程,进而构建了一种基于剖面隐马氏模型和量子粒子群优化算法的多序列比对算法。从核酸序列和BaliBASE比对数据库中选取了一些比对例子进行了模拟实验,并与其他算法进行了比较,结果表明,所提出的算法能在有限的时间内不仅能找到理想的隐隐马尔可夫模型,而且能得到最优的比对结果。

多序列比对;剖面隐马尔可夫模型;量子粒子群优化算法

核苷酸或氨基酸的多序列比对或联配是生物信息学中最重要、最具有挑战性的任务之一。多序列比对问题是一个将不等长的多个序列通过插入空位变成等长的过程,这些位置上的空位代表着相比对的序列从共同的祖先通过插入/删除操作的进化过程。利用多序列比对算法得到的最优比对,可用于找出蛋白质家族的模体(motifs)或保守区域(conserved domains),可用于预测蛋白质的结构和功能,也可用于进行系统发育的分析[1-2]。

目前主要有下列3种策略用于多序列比对。……