2003 · 12 citations · 12 references
Life SciencesBioinformaticsBiologyComputational BiologyGenomicsSequence AnalysisDynamic ProgrammingDynamic Programming For AlignmentSequence AlignmentSequence Similarity SearchString AlgorithmsAlignment OptimizationBest-first SearchBiological Sequence AlignmentComputational Alignment Algorithms
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.
12
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Depth-first iterative-deepening
Richard E. Korf · Artificial Intelligence · 1985 · 1.6K citations
A linear space algorithm for computing maximal common subsequences
D. S. Hirschberg · Communications of the ACM · 1975 · 1.1K citations · Full text