Multiple Protein Sequence Alignment using Parallel Iterative Algorithm
and A* Algorithm
Yasushi Totoki(1), Yutaka Akiyama(2), Kentaro Onizuka(2),
Tamotsu Noguchi(2), Minoru Saito(3), Makoto Ando(2)
Since the multiple sequence alignment problem requires enormous
calculation time, one is faced with a trade-off between computation
time and the quality of alignment. To date, although several
approximation methods have been proposed, the quality of alignments
produced by the previous methods is limited. As a new strategy, we
employed an iterative scheme with best-first search, and parallelized
its search step. 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 to be performed within reasonable
calculation time.