Employing A* Algorithm in Parallel Multiple Protein Sequence Alignment
Yasushi Totoki(1), Yutaka Akiyama(2), Kentaro Onizuka(2),
Tamotsu Noguchi(2), Minoru Saito(2), Makoto Ando(2)
As a new strategy for multiple sequence alignment, 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.