Aligning Multiple Protein Sequences by Parallel Hybrid Genetic Algorithm

Hung Dinh Nguyen[1] (ndhung@taurus.cs.miyazaki-u.ac.jp)
Ikuo Yoshihara[2] (yashiha@cs.miyazaki-u.ac.jp\\)
Kunihito Yamamori[2] (yamamori@cs.miyazaki-u.ac.jp)
Moritoshi Yasunaga[3] (yasunaga@is.tsukuba.ac.jp)

[1]Graduate School of Engineering, Miyazaki University, 1-1 Gakuen- Kibanadai-Nishi, Miyazaki 889-2192, Japan
[2]Faculty of Engineering, Miyazaki University, 1-1 Gakuen- Kibanadai-Nishi, Miyazaki 889-2192, Japan
[3]Institute of Information Systems and Electronics, University of Tsukuba, 1-1-1 Tennoudai, Tsukuba 305-8573, Japan

Abstract

This paper presents a parallel hybrid genetic algorithm (GA) for solving the sum-of-pairs multiple protein sequence alignment. A new chromosome representation and its corresponding genetic operators are proposed. A multi-population GENITOR-type GA is combined with local search heuristics. It is then extended to run in parallel on a multiprocessor system for speeding up. Experimental results of benchmarks from the BAliBASE show that the proposed method is superior to MSA, OMA, and SAGA methods with regard to quality of solution and running time. It can be used for finding multiple sequence alignment as well as testing cost functions.

[ Full-text PDF | Table of Contents ]