HGA-COFFEE:多序列比对问题的混合遗传算法求解

HGA-COFFEE : Aligning Multiple Sequences by Hybrid Genetic Algorithm

针对生物序列分析中的多序列比对问题,设计了一个求解多序列比对问题的混合遗传算法(与之相应的软件称为HGA COFFEE),该算法采用COFFEE函数作为个体的适应度函数,构造了5种新的遗传算子,包括1种选择算子,2种交叉算子和2种变异算子,其中一种变异算子基于COFFEE的一致性信息设计,以改善算法的整体搜索能力;另一种变异算子基于动态规划方法设计,以增强其局部搜索能力。最后,通过对BAliBASE中144个测试例的测试,证明该算法是有效的,与已有的算法相比,该算法对处于朦胧区和具有N/C末端延伸的序列比对问题有更强的问题求解能力。

For the multiple sequence alignment problem in molecular biological sequence analysis, a hybrid genetic algorithm and an associated software package called HGA-COFFEE are presented. The COFFEE function is used to measure individual fitness. Five novel genetic operators incluing a selection operator, two crossover operators and two mutation operators are designed. One of the mutation operators is designed based on the COFFEE＇s consistency information that can improve the global search ability, and another is realized by dynamic programming method that can improve individuals locally. Experimental results of the 144 benchmarks from the BAliBASE show that the programming method that can improve individuals locally. Experimental results of the 144 benchmarks from the BAliBASE show that the proposed algorithm is feasible. For datasets in twilight zone and comprising N/C terminal extensions, HGA-COFFEE generates better alignment as compared to other methods studied in this paper.