Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1239-1244.
Abstract
Sequence alignment is an important problem in computational biology. We compare two different approaches to the problem of optimally aligning two or more character strings: bounded dynamic programming (BDP), and divide-and-conquer frontier search (DCFS). The approaches are compared in terms of time and space requirements in 2 through 5 dimensions with sequences of varying similarity and length. While BDP performs better in two and three dimensions, it consumes more time a nd memory than DCFS for higher-dimensional problems.
@inproceedings{ijcai2003p176,
title = {Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment},
author = {Hohwald, Heath and Thayer, Ignacio and Korf, Richard E.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1239--1244},
year = {2003},
url = {https://ijcai.org/proceedings/2003/176},
}
TY - CPAPER TI - Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment AU - Hohwald, Heath AU - Thayer, Ignacio AU - Korf, Richard E. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1239 EP - 1244 UR - https://ijcai.org/proceedings/2003/176 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
