摘要
为了克服遗传算法应用于多序列比对时所遇到的比对序列数受限制以及比对寻优速度慢的缺点,提出了一种基于遗传算法的DNA多序列比对方法(GAMA);针对DNA多序列比对的特点,指出了传统遗传算法中的交叉操作将为序列比对带来沉重的计算负担;避开遗传算法通常所采用的遗传操作算子,设计了独特的遗传算子(插入删除算子和合并分离算子)、基于BLAST相似度评分方法和完全比对块加权的个体适应度值评价函数,采用了便于插入和删除操作以及相似度评分的基于字符和空位矩阵的染色体编码方案。本算法具有操作算子数量少,算子调用机制简明的特点。最后,给出了将GAMA应用于DNA多序列比对的算例,实验结果验证了本算法的可行性。
In order to solve the problems of both the alignment sequences number limitation and time-consuming which genetic algorithm will encounter in multiple sequence alignment, the authors propose a DNA multiple sequence alignment method based on genetic algorithm (GAMA). Aimed at the characteristics of DNA multiple sequence alignment, they point out that the traditional crossover operation will dramatically aggravate the computation burden of GA, and they adopt two new kinds of genetic operators (Indel & Undiv operators) in GAMA instead of the crossover and mutation operators used in normal GA. The BLAST similarity score matrix and an absolute alignment block weighed fitness evaluation function are adopted. The characters and gaps composed matrix, which is convenient for genetic operation as well as individual evaluation, are also adopted to coding the chromosome of population. There are only a few genetic operators in the scheme of this paper, of which the scheduling mechanism is also simple. This paper present an example of applying GAMA to DNA multiple-sequence alignment, the experiment results validate the feasibility of this algorithm.
出处
《北京工业大学学报》
CAS
CSCD
北大核心
2003年第1期19-22,共4页
Journal of Beijing University of Technology
基金
国家自然科学基金资助重点项目(60234020)
国家自然科学基金资助项目(50274003)
