An evolutionary progressive multiple sequence alignment

Farhana Naznin, Morikazu Nakamura, Takeo Okazaki, Yumiko Nakajima

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publication2007 IEEE Congress on Evolutionary Computation, CEC 2007
Number of pages8
Publication statusPublished - Dec 1 2007
Externally publishedYes
Event2007 IEEE Congress on Evolutionary Computation, CEC 2007 - , Singapore
Duration: Sept 25 2007Sept 28 2007


Other2007 IEEE Congress on Evolutionary Computation, CEC 2007

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Theoretical Computer Science


Dive into the research topics of 'An evolutionary progressive multiple sequence alignment'. Together they form a unique fingerprint.

Cite this