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%.