Memory-Efficient A* Heuristics for Multiple Sequence Alignment
- Matthew McNaughton, Dept. of Computing Science UofA
- Paul Lu, Department of Computing Science
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
- Duane Szafron, UofA CS
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.
Citation
M. McNaughton, P. Lu, J. Schaeffer, D. Szafron. "Memory-Efficient A* Heuristics for Multiple Sequence Alignment". National Conference on Artificial Intelligence (AAAI), Edmonton Alberta, pp 737-743, January 2002.| Keywords: | machine learning |
| Category: | In Conference |
BibTeX
@incollection{McNaughton+al:AAAI02,
author = {Matthew McNaughton and Paul Lu and Jonathan Schaeffer and Duane
Szafron},
title = {Memory-Efficient A* Heuristics for Multiple Sequence Alignment},
Pages = {737-743},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2002,
}Last Updated: April 24, 2007Submitted by Christian Smith
