Multiple Sequence Alignment Using Anytime A*

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Student Abstracts

We describe an extension of the A* algorithm, called Anytime A*, and show that it is effective in solving search problems that have a very large branching factor, such as the multiple sequence alignment problem in computational biology. We compare its performance to two other modified A* algorithms described in the literature and designed for the same class of problems. We show that Anytime A* offers a good time-space tradeoff.