Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment
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 and memory than DCFS for higher-dimensional problems.
Cite
Text
Hohwald et al. "Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment." International Joint Conference on Artificial Intelligence, 2003.Markdown
[Hohwald et al. "Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment." International Joint Conference on Artificial Intelligence, 2003.](https://mlanthology.org/ijcai/2003/hohwald2003ijcai-comparing/)BibTeX
@inproceedings{hohwald2003ijcai-comparing,
title = {{Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment}},
author = {Hohwald, Heath and Thayer, Ignacio and Korf, Richard E.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2003},
pages = {1239-1245},
url = {https://mlanthology.org/ijcai/2003/hohwald2003ijcai-comparing/}
}