## Application of Parallelized DP and A* Algorithm
to Multiple Sequence Alignment

Shiho ARAKI[1] (shiho@sucaba.ntt.jp)

Masahiro GOSHIMA[2] (goshima@kuis.kyoto-u.ac.jp)

Shin-ichiro MORI[2] (moris@kuis.kyoto-u.ac.jp)

Hiroshi NAKASHIMA[2] (nakasima@kuis.kyoto-u.ac.jp)

Shinji TOMITA[2] (tomita@kuis.kyoto-u.ac.jp)

Yutaka AKIYAMA[3]

Minoru KANEHISA[3]

[1]NTT Network Information System Laboratories

1-2356,Take,Yokosuka-shi, Kanagawa-ken, 238-03 Japan

[2]Department of Information Science, Faculty of Engineering, Kyoto University

Yoshida-hon-machi, Sakyo-ku, Kyoto 606- 01 Japan

[3]Institute for Chemical Research, Kyoto University

Gokasho, Uji, Kyoto 611 Japan

**Abstract**
This paper makes two proposals to speed up the Parallel Iterative Method, which is based on the iterative strategy of the Berger-Munson algorithm.

The first proposal is to exploit finer-grained parallelism in the DP(Dynamic Programming) procedure itself. This proposal makes the processing speed proportional to the number of processors.
The second proposal is to apply the A* algorithm, a well known heuristic search algorithm, instead of DP. A* reduces the search space using heuristics, while DP traverses the whole space blindly.
We have implemented these two proposals on a parallel computer, the AP1000. In a test of parallelizing DP, ten 1000-character sequences are aligned by using 10 processors per one DP procedure at a speed 8.11 times faster than sequential processing. By applying the A* algorithm to 30 sets of test problems, we obtain optimal alignment by reducing the search space by 95%.