An evolutionary progressive multiple sequence alignment

This paper proposes an evolutionary tree-base (progressive multiple sequence alignment) method using a genetic algorithm (GA) for solving multiple sequence alignment problems. In our evolutionary tree-base method, chromosomes are represented as guide trees. Two kinds of crossover are proposed for chromosomes of tree structure; subtree selection crossover and tree uniform order crossover. They can generate new chromosomes with inheriting tree structure of parents. The indirect representation of multiple alignments, namely, the guide tree representation of chromosomes, and the proper genetic operations make searching drastically efficient. Experimental results for benchmark problems from BAIiBASE and the NCBI database show that the proposed method is superior to SAGA (a well-known GA-base approach, 1996), T-Coffee (sensitive progressive method, 2000), MUSCLE (progressive/iterative method, 2004), MAFFT (progressive/iterative method, 2005), and ProbCons (probabilistic/consistency method, 2005) with regard to quality of solutions.