A dynamic programming algorithm to find all solutions in a neighborhood of the optimum
Mathematical BiosciencesPublished 1 December 1985
Michael S. Waterman, Thomas Byers
Citations74
SJR quartileQ2
SJR score0.56
SNIP0.82
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new technique is described which modifies the usual backtracking procedure and lists all near-optimal policies and is very much in the spirit of the original formulation of dynamic programming.
Abstract
Just after he introduced dynamic programming, Richard Bellman with R. Kalaba in 1960 gave a method for finding Kth best policies. Their method has been modified since then, but it is still not practical for many problems. This paper describes a new technique which modifies the usual backtracking procedure and lists all near-optimal policies. This practical algorithm is very much in the spirit of the original formulation of dynamic programming. An application to matching biological sequences is given.
Keywords
Computer Science
Journal of Molecular BiologyA general method applicable to the search for similarities in the amino acid sequence of two proteins
11,464 Citations1970Saul B. Needleman, Christian D. Wunsch
A computer adaptable method for finding similarities in the amino acid sequences of two proteins has been developed and it is possible to determine whether significant homology exists between the proteins to trace their possible evolutionary development.
Operations ResearchAn Appraisal of Some Shortest-Path Algorithms
997 Citations1969Stuart E. Dreyfus
This paper treats five discrete shortest-path problems: determining the shortest path between two specified nodes of a network, determining the second, third, etc., shortest path, finding the fastest path through a network with travel times depending on the departure time, and finding the shortest paths between specified endpoints that passes through specified intermediate nodes.
CERN Document Server (European Organization for Nuclear Research)Dynamic programming: Models and applications
413 Citations1982Eric V. Denardo
Journal of Molecular EvolutionComparative biosequence metrics
255 Citations1981Temple F. Smith, Michael S. Waterman +1 more
The sequence alignment algorithms of Needleman and Wunsch (1970) and Sellers (1974) are compared and the two procedures are proven to be equivalent.
Proceedings of the National Academy of SciencesOptimal sequence alignments
219 Citations1983Walter M. Fitch, Temple F. Smith
Most algorithms currently in use must fail to find the homologous alignment between a set of codons for the chicken alpha- and beta-hemoglobin sequence when it is in fact discoverable by a more general treatment of gaps.
Journal of the ACMA Method for the Solution of the <i>N</i> th Best Path Problem
205 Citations1959Walter Hoffman, Richard Pavley
A network is completely specified by a tabulat ion of its links which gives, for each link, a positive real number called the value of the link.
Bulletin of Mathematical BiologyGeneral methods of sequence comparison
162 Citations1984Michael S. Waterman
Journal of the Society for Industrial and Applied MathematicsOn<i>k</i>th Best Policies
106 Citations1960Richard Bellman, Robert E. Kalaba
NetworksIterative methods for determining the k shortest paths in a network
95 Citations1976Douglas R. Shier
On the basis of both theoretical and computational evidence, one of the three methods is seen to offer an extremely effective procedure for finding the k shortest paths from a given node in a network.
Operations ResearchTechnical Note—Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming
67 Citations1984Thomas Byers, Michael S. Waterman
This paper presents a new algorithm for finding all solutions with objective function values in the neighborhood of the optimum for certain dynamic programming models, including shortest path problems, which is the first practical algorithm for a variety of large problems that are of interest.
Proceedings of the National Academy of SciencesSequence alignments in the neighborhood of the optimum with general application to dynamic programming
64 Citations1983Michael S. Waterman
An algorithm has been developed to produce all alignments within a specified distance of the optimum within which the optimum is computed, and the algorithm can be repeated at will.
Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming
57 Citations1984Thomas Byers, Michael S. Waterman
Operations ResearchLetter to the Editor—The <i>k</i>th Best Route Through a Network
51 Citations1961Maurice Pollack
Lecture notes in economics and mathematical systemsSome Network Models in Management Science
44 Citations1970Salah E. Elmaghraby
The results suggest that the shortest path problems can be solved using networks of flow, but the properties of these networks and their generalizations are still poorly understood.
Operations ResearchData Structures and Computer Science Techniques in Operations Research
38 Citations1978Bennett L. Fox
Some important data structures and computer science techniques, and their applications to operations research problems are discussed, and some of which are novel are novel.
Journal of Research of the National Bureau of Standards Section B Mathematical SciencesComputational experience with an algorithm for finding the k shortest paths in a network
38 Citations1974Douglas R. Shier
INFOR Information Systems and Operational ResearchCalculating<i>K</i>th Shortest Paths
28 Citations1973Bennett L. Fox
IMA Journal of Applied MathematicsA Note on an Algebra for the <i>k</i> Best Routes in a Network
24 Citations1973Edward Minieka, Douglas R. Shier
Defense Technical Information Center (DTIC)Calculating K-TH Shortest Paths,
11 Citations1971Fox,B. L.
Management ScienceOn Elmaghraby's “The Theory of Networks and Management Science”
4 Citations1971Jin Y. Yen
This letter is to examine many points made in this paper regarding shortest path network problems and present some additional information on some of the problems being discussed in the original paper for the reader's reference.