Multiple Alignment using A* Algorithm and Parallel Iterative Algorithm
Yasushi Totoki(1), Yutaka Akiyama(2), Tamotsu Noguchi(2),
Kentaro Onizuka(2), Minoru Saito(2), Makoto Ando(2)
Multiple sequence alignment is an important and widely used technique
for sequence similarity analysis in molecular biology. Since the
problem requires enormous calculation time and memory space, several
approximation methods have been proposed. However the quality of
alignments by the previous methods are limited. As a new strategy, we
employed an iterative scheme with best-first search, and parallelized
its search step using PVM library. Furthermore we implemented the A*
pruning algorithm instead of dynamic programming, to drastically
reduce the search space. As a result, our new parallel system enables
biologically accurate multiple sequence alignment performed within
reasonable time.