A* with Partial Expansion for Large Branching Factor Problems

Abstract

The multiple sequence alignment problem is one of the im-portant problems in Genome Informatics. The notable fea-ture of this problem is that its state-space forms a lattice. Researchers have applied search algorithms such as A * and memory-bounded search algorithms including SNC to this problem. Unfortunately, previous work could align only seven sequences at most. Korf proposed DCBDS, which ex-ploits the features of a grid, and suggested that DCBDS prob-ably solved this problem, effectively. We found, however, that DCBDS was not effective for aligning many sequences. In this paper, we propose a simple and effective search algo-rithm, A * with Partial Expansion, for state-spaces with large branching factors. The aim of this algorithm is to store only necessary nodes for finding an optimal solution. In node ex-pansion, A * stores all child nodes, while our algorithm stores only promising child nodes. This mechanism enables us to re-duce the memory requirements during a search. We apply our algorithm to the multiple sequence alignment problem. It can align seven sequences with only 4.7 % of the stored nodes re-quired by A*.