资源描述：
《一种基于遗传算法的DNA多序列比对方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第卷第期北京工业大学学报年月、尸一种基于遗传算法的多序列比对方法龚道雄,阮晓钢北京工业大学电子信息与控制工程学院,北京摘要为了克服遗传算法应用于多序列比对时所遇到的,比对序列数受限制以及比对寻优速度慢的缺点提出了一种基于遗传算法的〕,〕多序列比对方法针对多序列比对的特点指出了传统遗传算法中的交叉操作将为序列比对带来沉重的计算负担避开遗传算法通常所采用的遗传操作算子,设计了独特的遗传、算子插人删除算子和合并分离算子基于相似度评分方法和完全比对块加权的个体适应度值评价函数,采用了便于插人和删除操作以及相似度评分的基于字符和空位矩阵的染色体编码方案本算
2、法具有操作算子数量少,算子调用机制简明的特点最后,给出了将应用于多序列比对的算例,实验结果验证了本算法的可行性关键词遗传算法多序列比对遗传算子一一一中图分类号文献标识码文章编号多序列比对是现代生物序列分析的重要内容通过多序列比对,可以预测新序列的结构和功能,可以分析序列之间的同源关系,以及进行系统发育分析多序列比对是一个具有极高计算复杂度的组合优化问题川遗传算法是一种建立在自然选择和进化进程概念基础之上的求解复杂系统优化间题的通用方法,该方法因具有不易陷人局部极小,能处理大型搜索空间,易于与其他优化方法结合,以及几乎适〕用于所有连续和离散优化问题
3、的特点而获得了广泛的应用一些研究者就基于遗传算法的多序列比一’,对方法进行了有益的探索和的通过定义了种遗传操作算子以及算子间的自动调用方法取得了较好的多序列比对质量,但当参与比对序列达到个以上时比对的速度就非’常慢和司研究了基于并行遗传算法的多序列比对方法【‘〕和等将动态规划方法和遗传算法相结合进行多序列比对,但只对于具有高度“〕相似性的长序列在序列数量较少时才能取得较好的结果虽然上述研究在一些方面取得了满意的结果,遗传算法应用于多序列比对尚有许多问题有待于进一步的研究和探索问题多序列比对的目标是使得参与比对的序列中有尽可能多的列具有相同的字符,
4、即使得具有相同碱基的位点位于同一列,这样便于发现不同序列之间的相似部分,从而推断它们在功能和结构上的相似性问题描述多序列比对过程可以表示成为一个五元组艺,,月,,二‘,’月,,,,其中艺艺为多序列比对的符号集艺,为组成的种碱基为空位符,二‘二,,表示比对中插人的空位为待比对的序列集每个序列由数量不等的字符组成笼··,,‘‘,,‘丁,,‘‘‘’一’’’’艺’月⋯梦代心一弓其中为序列的长度弓为序列中的第个字符·。。,,,胡代、艺为多序列比对的结果矩阵其中矩阵的每一列为一个位点上的比对矩阵的第行对应学基金资助重点项目国家自然科学基金资助项目囊望暴臀爵着
5、稀作者简介龚道雄一,男,博士生北京工业大学学报年,于参与比对的第个序列序列中非空位字符的先后顺序在比对中不能改变为基本比对操作集,口斑,,即插人和删除空位操作为在基本操作集之上实现最优比对的策略,它确定一系列在特定位点上的空位插人和删除操作即为所研究的中心问题算法可用一个四元组表示,,及,其中及为选择操作算子,实现从群体中选择个体进行繁殖的功能为插人删除操作算子,实,现空位的插人和删除功能为合并和分离操作算子实现特定的子字符串的移动功能为遗传算法的评价函数在本算法中,每代,的群体规模是固定的每代所产生的个体均加人到群体中与父代共同竞争适应度值低的
6、个体被淘汰算法。编码方法为了遗传操作和评价的方便,在本算法中直接应用由字符和空位组成的矩阵表示一个比对方案,作为遗传算法中的一个个体,,。。。月‘艺,,其中为参与比对的序列数为序列长度短序列通过在序列的尾部插人空位补足例如两序列比对问题中,况,凡一,则个体的初始编码为选择算子为了防止因为超级个体的存在而使算法过早收敛,本算法在选择个体进行繁殖时采取如下策略高于当代平均适应度值一个标准偏差的个体给定两次繁殖机会低于当代平均适应度值一个标准偏差的个体给定零次繁殖机会其余的给定一次繁殖机会遗传操作算子因为多序列比对不允许改变比对序列中非空位字符串的相对
7、顺序,所以当采用交叉操作并且参与操作的两个个体中有一个的交叉点选定之后,另一个就不能再任意的选取,而且在另一个个体中确定交叉点时还需要进行多次串匹配和比较操作设参与比对的序列数为,序列的最大长度为,遗传算法的群体尸,,、,·尸、规模为遗传操作的最大代数为交叉概率加则在一次遗传操作中将进行次平均字符串长度为的字符串比较多序列比对的这个特点使得采用交叉算子将耗费大量的计算,极大地增加了计算复杂性交叉算子的使用是使得遗传算法在求解多序列比对问题时速度慢和可比对的序列数受限制的主要原因因此,在本文中取消了交叉操作算子算子算子包括插人和删除两个算子插人和删
8、除操作单对空位而言当满足插人概率时,向序列中随机地插人一个空位当满足删除概率时,从序列中删除随机选定的空位插人和删除的概率相对较大在一个
