(75) Multiple Sequence Alignment by Parallel Iterative Aligner

	Machine:     PIM/m
	Environment: PIMOS
	Language:    KL1
	Source Code: 0.42 MB
	Documents:   Manual (Japanese)

Overview

The system partially improves temporary alignment in an iterative way, and can effectively achieve high-quality alignment as a result.

Features

Multiple branches of a search tree in this combinatorial problem are evaluated in parallel by using many processing elements in each iteration.

The heuristic method, `Restricted Partitioning Technique', prunes a large number of branches from the search tree and makes it possible to solve the combinatorial problem in a practical amount of time.

Function

This system solves, for example, an alignment of 22 sequences, each of which has 80 amino acids, in about 10 minutes, when using PIM/m with 256 processing elements(PEs).

In the restricted partitioning technique, the number of sequences in the smaller devided group is restricted to one or two. 253 PEs(combinations of 1 from 22 plus combinations of 2 from 22) are used to execute all restricted partitioning in parallel. Additionally, one processor is used for a manager process which selects the best alignment in every iteration. In total, 254 PEs are employed when 22-sequence alignment is solved.

FTP

www-admin@icot.or.jp