计算机应用 ›› 2010, Vol. 30 ›› Issue (1): 146-149.

• 人工智能 • 上一篇    下一篇

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

张琎1,张远2   

  1. 1. 山东济南大学信息科学与工程学院
    2. 济南大学
  • 收稿日期:2009-07-16 修回日期:2009-09-05 发布日期:2010-01-01 出版日期:2010-01-01
  • 通讯作者: 张琎
  • 基金资助:
    国家自然科学基金资助项目;济南大学科研基金项目

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

  • Received:2009-07-16 Revised:2009-09-05 Online:2010-01-01 Published:2010-01-01

摘要: 多序列比对问题是生物信息学中尚未解决的一个NP完全的组合优化问题。通过对重新组装的空位矩阵进行遗传操作来实现最优比对,设计了一个新型的基于GC-GM的多序列比对穷举遗传算法。从BAliBASE 比对数据库中选取了一些比对例子进行了模拟计算,并与Clustal-W算法进行了比较,实验表明该算法是有效的。

关键词: 生物信息学, 多序列比对, 空位, 交叉

Abstract: 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.

Key words: bioinformatics, Multiple Sequence Alignment (MSA), gap, crossover