Improvement of the A* Algorithm for Multiple Sequence Alignment

Hirotada Kobayashi (
Hiroshi Imai (

Department of Information Science, Faculty of Science, University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan


The alignment problem of DNA or protein sequences is very applicable and important in various fields of molecular biology. This problem can be reduced to the shortest path problem and Ikeda and Imai showed that the A* algorithm works efficiently with the estimator utilizing all 2-dimensional sub-alignments.

In this paper we present new powerful estimators utilizing K≥3 dimensional sub-alignments, and propose a new bounding technique using VD , a set of vertices in the paths whose lengths are at most D longer than the shortest path. We also extend our algorithm to a recursive-estimate version. These algorithms become more efficient when the number of sequences increase, or the similarity among sequences is lower.

[ Full-text PDF | Table of Contents ]

Japanese Society for Bioinformatics