Improvement of the A(*) Algorithm for Multiple Sequence Alignment

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 (Genome Informatics 5: 90-99, 1994) 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 V (Delta), a set of vertices in the paths whose lengths are at most Delta 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.