MASATO ISHIKAWA[1] (ishikawa@icot.or.jp)
TOMOYUKI TOYA[1] (toya@icot.or jp)
YASUSHI TOTOKI[1] (totoki@icot.or.jp)
AKIHIKO KONAGAYA[2] (konagaya@csl.cl.nec.co.jp)
[1]Institute for New Generation Computer Technology (ICOT)
1-4-28 Mita, Minato-ku, Tokyo 108 JAPAN
[2]C&C Systems Research Laboratories, NEC Corporation
4-1-1, Miyazaki, Miyamae-ku, Kawasaki, Kanagawa 216 Japan
This paper proposes a new methodology to improve the performance of multiple sequence alignment by combining a genetic algorithm and an iterative alignment algorithm. Iterative alignment algorithms usually achieve better alignment than other alignment algorithms, such as tournament based multiple alignment. They, also, can incorporate parallelism to improve execution performance. However, they sometimes suffer from being trapped in the local optima and result in relatively low-quality alignments due to their rapid convergence. A genetic algorithm can save this problem by exchanging partial alignment sequences between "individuals". Our experiments show that the combination of a genetic algorithm and an iterative alignment algorithm produces better results than iterative aligners which employ hill-climbing search strategies.