(94) Multiple Sequence Alignment by Genetic Algorithm

	Machine:     PIM/UNIX Machine
	Environment: PIMOS/UNIX, KLIC
	Language:    KL1
	Source Code: 0.3 MB
	Documents:   Manual (English / Japanese)

Overview

This parallel system, the combination of a genetic algorithm and an iterative alignment algorithm, produces better results than iterative aligners which employ hill-climbing search strategies.

Features

This parallel alignment system featuring a genetic algorithm can improve an alignment score as rapidly as that with the hill-climbing algorithm, and the system gradually increased the score to a higher level which might be close to the optimal alignment score. The reason why the genetic algorithm shows such high performance seems to be the modularity of multiple alignment problems. If we can replace a part of a sequence alignment with a better part from another, we obtain a better multiple sequence alignment. Crossover operators achieve this replacement in a statistical manner.

Function

In this system, each individual alignment is assigned to a PE, so the size of population is 255 when using PIM/m with 256 PEs. A PE is used as a manager process to select discarded individuals and crossover candidates. The period of each generation is controlled with the system timer, whose default value is eighty seconds. When each PE finds that the system timer has passed eighty seconds, it does not apply another mutation operator but sends the current alignment to the manager PE. On average, four mutations occur in a generation with the crossover operation, or six mutations occur in a generation without it. The maximum alignment score among the population is decided as having converged when it is invariable through more than one hundred generations. It took about two hours to obtain the converged score when solving a practical-scale alignment problem, which consists of twenty-two sequences with eighty amino-acid letters each.

This system can also execute on computers with basic functions of UNIX operating system using KLIC.

FTP

www-admin@icot.or.jp