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

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