基于GC-GM的多序列比对穷举遗传算法  

Exhaustive genetic algorithm based on GC-GM for multiple sequence alignment

作　　者：张琎[1] 张远[1] 

机构地区：[1]济南大学信息科学与工程学院,济南250022

出　　处：《计算机应用》2010年第1期146-149,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60573065);济南大学科研基金资助项目(XKY0821)

摘　　要：多序列比对问题是生物信息学中尚未解决的一个NP完全的组合优化问题。通过对重新组装的空位矩阵进行遗传操作来实现最优比对,设计了一个新型的基于GC-GM的多序列比对穷举遗传算法。从BAliBASE比对数据库中选取了一些比对例子进行了模拟计算,并与Clustal W算法进行了比较,实验表明该算法是有效的。Multiple sequence alignment is an unsolved NP-complete combinatorial optimization problem. This paper described a new exhaustive genetic algorithm based on Gap Crossover and Gap Mutation （GC-GM） for multiple sequence alignment by genetic operation on gap matrixes reassembled. The approach was examined by using a set of standard instances taken from the benchmark alignment database BAliBASE. Numerical simulation results were compared with those obtained by using the Clustal W algorithm and showed the effectiveness of the new approach.

关 键 词：生物信息学 多序列比对 空位 交叉 变异 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]