Memory-Efficient A* Heuristics for Multiple Sequence Alignment
The time and space needs of an A* search are strongly influenced by the quality
of the heuristic evaluation function. Usually there is a trade-off since better
heuristics may require more time and/or space to evaluate. Multiple sequence
alignment is an important application for single-agent search. The traditional
heuristic uses multiple pairwise alignments that require relatively little space.
Three-way alignments produce better heuristics, but they are not used in practice
due to the large space requirements. This paper presents a memory-efficient
way to represent three-way heuristics as an octree. The required portions of
the octree are computed on demand. The octree-supported three-way heuristics
result in such a substantial reduction to the size of the A* open list that
they offset the additional space and time requirements for the three-way alignments.
The resulting multiple sequence alignments are both faster and use less memory
than using A* with traditional pairwise heuristics.