Proceedings

Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1239-1244.

© 2003 International Joint Conferences on Artificial Intelligence

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.

  1. [Dijkstra, 1959] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1 :269- 271, 1959.
  2. [Durbin eta!., 1998] R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological sequence analysis. Cambridge University Press, 1998. ISBN: 0-521-62971-3.
  3. [Hart eta!. , 1968] P.E. Hart, N.J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Science and Cybernetics, SSC-4(2): 100-107, July 1968.
  4. [Hirschberg, 1975] D. S. Hirschberg. A linear space algo- rithm for computing longest common subsequences. Com - munications of the ACM, 18:341-343, 1975.
  5. [Hirschberg, 1997] D. S. Hirschberg. Serial computations of Levenshtein distances. In A. Apostolico and Z. Galil, ed- itors, Pattern matching algorithms, chapter 4, pages 123- 141. Oxford University Press, 1997.
  6. [Korf and Zhang, 2000] Richard E. Korf and Weixiong Zhang. Divide-and-conquer frontier search applied to op- timal sequence alignment. In Proceedings of the 7th Con- ference on Artificial Intelligence (AAAI-00) and of the 12th Conference on Innovative Applications of Artificial Intel- ligence (JAAJ-00), pages 910-916, Menlo Park, CA, July 30-3 2000. AAAI Press.
  7. [Korf, 1985] Richard E. Korf. Depth-first iterative- deepening: An optimal admissible tree search. Artificial intelligence, 27(1):97-109, 1985. Reprinted in Chapter 6
  8. of Expert Systems, A Software Methodology for Modern Applications, P.G. Raeth (Ed.), IEEE Computer Society Press, Washington D.C., 1990, pp. 380-389.
  9. [Korf, 1999] Richard E. Korf. A divide and conquer bidi- rectional search: First results. In Dean Thomas, editor, Proceedings of the 16th International Joint Conference on Artificial intelligence (JJCAI-99-Vo/2), pages 1184-1191, S.F., July 31-August 6 1999. IJCAI
  10. [McNaughton eta!., 2002] Matthew McNaughton, Paul Lu, Jonathan Schaeffer, and Duane Szafron. Memory-efficient A* heuristics for multiple sequence alignment. Proceed- ings of the Eighteenth National Conference on Artificial Intelligence, July-August 2002.
  11. [Needleman and Wunsch, 1970] S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Bioi., 48:443-453, 1970.
  12. [Spouge, 1989] J. L. Spouge. Speeding up dynamic pro- gramming algorithms for finding optimal lattice paths. SIAM J. Appl. Math., 49(5): 1552-1566, October 1989.
  13. [Thomson eta!., 1999] J.D. Thomson, F. Plewniak, and 0 . Poch. BAliBASE: a benchmark alignment database for SEARCH the evaluation of multiple alignment programs. Bioinfor- matics, 15(1):87-88, 1999.
  14. [Ukkonen, 1985] E. Ukkonen. Algorithms for approximate string matching. Information and Control, 64:100-118, 1985.
  15. [Waterman, 1995] M. S. Waterman. Introduction to Compu- tational Biology. Chapman & Hall, 1995.
  16. [Zhang, 2002] Weixiong Zhang. Personal communication, August 2002.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards