Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “Dynamic Programming”

Search indexed PubMed citations on genomics, clinical trials, systematic reviews and public health. Explore titles, authors and supplied subject terms, then open the PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 recordsLinked to original sources
PubMed2004

Checkpoint method for choice recovery in dynamic programming.

Many dynamic programming algorithms consist of a 'forward pass' computation to optimize a cost function, followed by a 'choice recovery' computation to construct a configuration that optimizes the cost function. 'Checkpointing' is a method to perform choice recovery using limited storage. During a forward pass, checkpoints in an optimal configuration are identified. Then recursion is used to fill in the portions of an optimal configuration between successive checkpoints. Choosing the number of checkpoints to use mediates a tradeoff between storage and speed.

Algorithms↗
PubMed1995

Human-like dynamic programming neural networks for dynamic time warping speech recognition.

This paper presents a human-like dynamic programming neural network method for speech recognition using dynamic time warping. The networks are configured, much like human's, such that the minimum states of the network's energy function represent the near-best correlation between test and reference patterns. The dynamics and properties of the neural networks are analytically explained. Simulations for classifying speaker-dependent isolated words, consisting of 0 to 9 and A to Z, show that the method is better than conventional methods. The hardware implementation of this method is also presented.

Humans↗
PubMed2000

A systematic approach to dynamic programming in bioinformatics.

MOTIVATION: Dynamic programming is probably the most popular programming method in bioinformatics. Sequence comparison, gene recognition, RNA structure prediction and hundreds of other problems are solved by ever new variants of dynamic programming. Currently, the development of a successful dynamic programming algorithm is a matter of experience, talent and luck. The typical matrix recurrence relations that make up a dynamic programming algorithm are intricate to construct, and difficult to implement reliably. No general problem independent guidance is available. RESULTS: This article introduces a systematic method for constructing dynamic programming solutions to problems in biosequence analysis. By a conceptual splitting of the algorithm into a recognition and an evaluation phase, algorithm development is simplified considerably, and correct recurrences can be derived systematically. Without additional effort, the method produces an early, executable prototype expressed in a functional programming language. The method is quite generally applicable, and, while programming effort decreases, no overhead in terms of ultimate program efficiency is incurred.

Algorithms↗
PubMed1983

Sequence alignments in the neighborhood of the optimum with general application to dynamic programming.

When applying dynamic programming techniques to obtain optimal sequence alignments, a set of weights must be assigned to mismatches, insertion/deletions, etc. These weights are not predetermined, although efforts are being made to deduce biologically meaningful values from data. In addition, there are sometimes unknown constraints on the sequences that cause the "true" alignment to disagree with the optimum (computer) solution. To assist in overcoming these difficulties, an algorithm has been developed to produce all alignments within a specified distance of the optimum. The distance can be chosen after the optimum is computed, and the algorithm can be repeated at will. Earlier algorithms to solve this problem were very complex and not practical for any case involving sequences with significant time or storage requirements. The algorithm presented here overcomes these difficulties and has application to general, discrete dynamic programming problems.

Journal Article↗
PubMed2005

Versatile and declarative dynamic programming using pair algebras.

BACKGROUND: Dynamic programming is a widely used programming technique in bioinformatics. In sharp contrast to the simplicity of textbook examples, implementing a dynamic programming algorithm for a novel and non-trivial application is a tedious and error prone task. The algebraic dynamic programming approach seeks to alleviate this situation by clearly separating the dynamic programming recurrences and scoring schemes. RESULTS: Based on this programming style, we introduce a generic product operation of scoring schemes. This leads to a remarkable variety of applications, allowing us to achieve optimizations under multiple objective functions, alternative solutions and backtracing, holistic search space analysis, ambiguity checking, and more, without additional programming effort. We demonstrate the method on several applications for RNA secondary structure prediction. CONCLUSION: The product operation as introduced here adds a significant amount of flexibility to dynamic programming. It provides a versatile testbed for the development of new algorithmic ideas, which can immediately be put to practice.

Algorithms↗
PubMed1992

Dynamic programming algorithms for biological sequence comparison.

Efficient dynamic programming algorithms are available for a broad class of protein and DNA sequence comparison problems. These algorithms require computer time proportional to the product of the lengths of the two sequences being compared [O(N2)] but require memory space proportional only to the sum of these lengths [O(N)]. Although the requirement for O(N2) time limits use of the algorithms to the largest computers when searching protein and DNA sequence databases, many other applications of these algorithms, such as calculation of distances for evolutionary trees and comparison of a new sequence to a library of sequence profiles, are well within the capabilities of desktop computers. In particular, the results of library searches with rapid searching programs, such as FASTA or BLAST, should be confirmed by performing a rigorous optimal alignment. Whereas rapid methods do not overlook significant sequence similarities, FASTA limits the number of gaps that can be inserted into an alignment, so that a rigorous alignment may extend the alignment substantially in some cases. BLAST does not allow gaps in the local regions that it reports; a calculation that allows gaps is very likely to extend the alignment substantially. Although a Monte Carlo evaluation of the statistical significance of a similarity score with a rigorous algorithm is much slower than the heuristic approach used by the RDF2 program, the dynamic programming approach should take less than 1 hr on a 386-based PC or desktop Unix workstation. For descriptive purposes, we have limited our discussion to methods for calculating similarity scores and distances that use gap penalties of the form g = rk. Nevertheless, programs for the more general case (g = q+rk) are readily available. Versions of these programs that run either on Unix workstations, IBM-PC class computers, or the Macintosh can be obtained from either of the authors.

Algorithms↗
PubMed2005

Myocardial border detection by branch-and-bound dynamic programming in magnetic resonance images.

Dynamic programming (DP) is a mathematical technique for making optimal decisions on the sequencing of interrelated problems. It has been used widely to detect borders in magnetic resonance images (MRI). MRI is noninvasive and generates clear images; however, it is impractical for manual measurement of the huge number of images generated by dynamic organs such as those of the cardiovascular system. A fast and effective algorithm is essential for on-line implementation of MRI-based computer aided measurement and diagnosis. In this paper, a branch-and-bound dynamic programming technique is applied to detect the endocardial borders of the left ventricular. The proposed branch-and-bound method drastically reduces the computational time required in conventional exhaustive search methods. Statistical tests are conducted to verify the CPU time performance of the branch-and-bound technique in comparison to the conventional exhaustive search method.

Computers↗
PubMedDate not supplied

Proper orthogonal decomposition based optimal neurocontrol synthesis of a chemical reactor process using approximate dynamic programming.

The concept of approximate dynamic programming and adaptive critic neural network based optimal controller is extended in this study to include systems governed by partial differential equations. An optimal controller is synthesized for a dispersion type tubular chemical reactor, which is governed by two coupled nonlinear partial differential equations. It consists of three steps: First, empirical basis functions are designed using the 'Proper Orthogonal Decomposition' technique and a low-order lumped parameter system to represent the infinite-dimensional system is obtained by carrying out a Galerkin projection. Second, approximate dynamic programming technique is applied in a discrete time framework, followed by the use of a dual neural network structure called adaptive critics, to obtain optimal neurocontrollers for this system. In this structure, one set of neural networks captures the relationship between the state variables and the control, whereas the other set captures the relationship between the state and the costate variables. Third, the lumped parameter control is then mapped back to the spatial dimension using the same basis functions to result in a feedback control. Numerical results are presented that illustrate the potential of this approach. It should be noted that the procedure presented in this study can be used in synthesizing optimal controllers for a fairly general class of nonlinear distributed parameter systems.

Models, Chemical↗
PubMed1999

The effect of variability in the food supply on the daily singing routines of European robins: a test of a stochastic dynamic programming model.

A stochastic dynamic programming (SDP) model offers a general explanation of daily singing routines in birds, but remains almost untested empirically. I examined a central prediction of the SDP model, that a more variable food supply decreases the bird's song output at dawn, relative to its song output at dusk. I provided supplementary food to make the food supply more or less variable over 2-week periods in the territories of free-living European robins Erithacus rubecula. Robins sang relatively less at dawn than at dusk after weeks in which their supplementary food supply was variable, and more at dawn than at dusk after weeks in which their food supplementation was constant. These results provide strong support for the prediction of the SDP model. Copyright 1999 The Association for the Study of Animal Behaviour.

Journal Article↗
PubMed2000

Ways to test stochastic dynamic programming models empirically.

Stochastic dynamic programming (SDP) models are widely used to predict optimal behavioural and life history strategies. We discuss a diversity of ways to test SDP models empirically, taking as our main illustration a model of the daily singing routine of birds. One approach to verification is to quantify model parameters, but most SDP models are schematic. Because predictions are therefore qualitative, testing several predictions is desirable. How state determines behaviour (the policy) is a central prediction that should be examined directly if both state and behaviour are measurable. Complementary predictions concern how behaviour and state change through time, but information is discarded by considering behaviour rather than state, by looking only at average state rather than its distribution, and by not following individuals. We identify the various circumstances in which an individual's state/behaviour at one time is correlated with its state/behaviour at a later time. When there are several state variables the relationships between them may be informative. Often model parameters represent environmental conditions that can also be viewed as state variables. Experimental manipulation of the environment has several advantages as a test, but a problem is uncertainty over how much the organism's policy will adjust. As an example we allow birds to use different assumptions about how well past weather predicts future weather. We advocate mirroring planned empirical investigations on the computer to investigate which manipulations and predictions will best test a model. Copyright 2000 The Association for the Study of Animal Behaviour.

Journal Article↗
PubMed1993

Identification of coding regions in genomic DNA sequences: an application of dynamic programming and neural networks.

Dynamic programming (DP) is applied to the problem of precisely identifying internal exons and introns in genomic DNA sequences. The program GeneParser first scores the sequence of interest for splice sites and for these intron- and exon-specific content measures: codon usage, local compositional complexity, 6-tuple frequency, length distribution and periodic asymmetry. This information is then organized for interpretation by DP. GeneParser employs the DP algorithm to enforce the constraints that introns and exons must be adjacent and non-overlapping and finds the highest scoring combination of introns and exons subject to these constraints. Weights for the various classification procedures are determined by training a simple feed-forward neural network to maximize the number of correct predictions. In a pilot study, the system has been trained on a set of 56 human gene fragments containing 150 internal exons in a total of 158,691 bps of genomic sequence. When tested against the training data, GeneParser precisely identifies 75% of the exons and correctly predicts 86% of coding nucleotides as coding while only 13% of non-exon bps were predicted to be coding. This corresponds to a correlation coefficient for exon prediction of 0.85. Because of the simplicity of the network weighting scheme, generalization performance is nearly as good as with the training set.

Algorithms↗
PubMed2002

A dynamic programming algorithm for haplotype block partitioning.

We develop a dynamic programming algorithm for haplotype block partitioning to minimize the number of representative single nucleotide polymorphisms (SNPs) required to account for most of the common haplotypes in each block. Any measure of haplotype quality can be used in the algorithm and of course the measure should depend on the specific application. The dynamic programming algorithm is applied to analyze the chromosome 21 haplotype data of Patil et al. [Patil, N., Berno, A. J., Hinds, D. A., Barrett, W. A., Doshi, J. M., Hacker, C. R., Kautzer, C. R., Lee, D. H., Marjoribanks, C., McDonough, D. P., et al. (2001) Science 294, 1719-1723], who searched for blocks of limited haplotype diversity. Using the same criteria as in Patil et al., we identify a total of 3,582 representative SNPs and 2,575 blocks that are 21.5% and 37.7% smaller, respectively, than those identified using a greedy algorithm of Patil et al. We also apply the dynamic programming algorithm to the same data set based on haplotype diversity. A total of 3,982 representative SNPs and 1,884 blocks are identified to account for 95% of the haplotype diversity in each block.

Algorithms↗
PubMed1997

Introduction of a distance cut-off into structural alignment by the double dynamic programming algorithm.

Two approximations were introduced into the double dynamic programming algorithm, in order to reduce the computational time for structural alignment. One of them was the so-called distance cut-off, which approximately describes the structural environment of each residue by its local environment. In the approximation, a sphere with a given radius is placed at the center of the side chain of each residue. The local environment of a residue is constituted only by the residues with side chain centers that are present within the sphere, which is expressed by a set of center-to-center distances from the side chain of the residue to those of all the other constituent residues. The residues outside the sphere are neglected from the local environment. Another approximation is associated with the distance cut-off, which is referred to here as the delta N cut-off. If two local environments are similar to each other, the numbers of residues constituting the environments are expected to be similar. The delta N cut-off was introduced based on the idea. If the difference between the numbers of the constituent residues of two local environments is greater than a given threshold value, delta N, the evaluation of the similarity between the local environments is skipped. The introduction of the two approximations dramatically reduced the computational time for structural alignment by the double dynamic programming algorithm. However, the approximations also decreased the accuracy of the alignment. To improve the accuracy with the approximations, a program with a two-step alignment algorithm was constructed. At first, an alignment was roughly constructed with the approximations. Then, the epsilon-suboptimal region for the alignment was determined. Finally, the double dynamic programming algorithm with full structural environments was applied to the residue pairs within the epsilon-suboptimal region to produce an improved alignment.

Algorithms↗
PubMed1986

A dynamic programming algorithm for finding alternative RNA secondary structures.

Dynamic programming algorithms that predict RNA secondary structure by minimizing the free energy have had one important limitation. They were able to predict only one optimal structure. Given the uncertainties of the thermodynamic data and the effects of proteins and other environmental factors on structure, the optimal structure predicted by these methods may not have biological significance. We present a dynamic programming algorithm that can determine optimal and suboptimal secondary structures for an RNA. The power and utility of the method is demonstrated in the folding of the intervening sequence of the rRNA of Tetrahymena. By first identifying the major secondary structures corresponding to the lowest free energy minima, a secondary structure of possible biological significance is derived.

Animals↗
PubMed2004

A new 2D segmentation method based on dynamic programming applied to computer aided detection in mammography.

Mass segmentation plays a crucial role in computer-aided diagnosis (CAD) systems for classification of suspicious regions as normal, benign, or malignant. In this article we present a robust and automated segmentation technique--based on dynamic programming--to segment mass lesions from surrounding tissue. In addition, we propose an efficient algorithm to guarantee resulting contours to be closed. The segmentation method based on dynamic programming was quantitatively compared with two other automated segmentation methods (region growing and the discrete contour model) on a dataset of 1210 masses. For each mass an overlap criterion was calculated to determine the similarity with manual segmentation. The mean overlap percentage for dynamic programming was 0.69, for the other two methods 0.60 and 0.59, respectively. The difference in overlap percentage was statistically significant. To study the influence of the segmentation method on the performance of a CAD system two additional experiments were carried out. The first experiment studied the detection performance of the CAD system for the different segmentation methods. Free-response receiver operating characteristics analysis showed that the detection performance was nearly identical for the three segmentation methods. In the second experiment the ability of the classifier to discriminate between malignant and benign lesions was studied. For region based evaluation the area Az under the receiver operating characteristics curve was 0.74 for dynamic programming, 0.72 for the discrete contour model, and 0.67 for region growing. The difference in Az values obtained by the dynamic programming method and region growing was statistically significant. The differences between other methods were not significant.

Aged↗
PubMed1999

Protein threading by recursive dynamic programming.

We present the recursive dynamic programming (RDP) method for the threading approach to three-dimensional protein structure prediction. RDP is based on the divide-and-conquer paradigm and maps the protein sequence whose backbone structure is to be found (the protein target) onto the known backbone structure of a model protein (the protein template) in a stepwise fashion, a technique that is similar to computing local alignments but utilising different cost functions. We begin by mapping parts of the target onto the template that show statistically significant similarity with the template sequence. After mapping, the template structure is modified in order to account for the mapped target residues. Then significant similarities between the yet unmapped parts of the target and the modified template are searched, and the resulting segments of the target are mapped onto the template. This recursive process of identifying segments in the target to be mapped onto the template and modifying the template is continued until no significant similarities between the remaining parts of target and template are found. Those parts which are left unmapped by the procedure are interpreted as gaps. The RDP method is robust in the sense that different local alignment methods can be used, several alternatives of mapping parts of the target onto the template can be handled and compared in the process, and the cost functions can be dynamically adapted to biological needs. Our computer experiments show that the RDP procedure is efficient and effective. We can thread a typical protein sequence against a database of 887 template domains in about 12 hours even on a low-cost workstation (SUN Ultra 5). In statistical evaluations on databases of known protein structures, RDP significantly outperforms competing methods. RDP has been especially valuable in providing accurate alignments for modeling active sites of proteins.RDP is part of the ToPLign system (GMD Toolbox for protein alignment) and can be accessed via the WWW independently or in concert with other ToPLign tools at http://cartan.gmd.de/ToPLign.html.

Amino Acid Sequence↗
PubMedDate not supplied

[A rapid and precise method for lattice approximation of the course of a protein chain based on a dynamic programming algorithm].

Application of a dynamic programming method allows one to find the best possible lattice model of a protein chain fold for any lattice and any orientation of the protein relative to the lattice. Special repulsive potentials help to obtain the self-avoiding lattice models of protein folds. The quality of approximation increases when the distance between neighbor chain links is not fixed rigidly. The calculations carried out for the proteins of different structural classes show a high efficiency and precision of this method in comparison with other ones.

Algorithms↗
PubMed2003

Dynamic programming generation of boundaries of local coordinatized submanifolds in the neocortex: application to the planum temporale.

Dynamic programming is used to define boundaries of cortical submanifolds with focus on the planum temporale (PT) of the superior temporal gyrus (STG), which has been implicated in a variety of neuropsychiatric disorders. To this end, automated methods are used to generate the PT manifold from 10 high-resolution MRI subvolumes ROI masks encompassing the STG. A procedure to define the subvolume ROI masks from original MRI brain scans is developed. Bayesian segmentation is then used to segment the subvolumes into cerebrospinal fluid, gray matter (GM), and white matter (WM). 3D isocontouring using the intensity value at which there is equal probability of GM and WM is used to reconstruct the triangulated graph representing the STG cortical surface, enabling principal curvature at each point on the graph to be computed. Dynamic programming is used to delineate the PT manifold by tracking principal curves from the retro-insular end of the Heschl's gyrus (HG) to the STG, along the posterior STG up to the start of the ramus and back to the retro-insular end of the HG. A coordinate system is then defined on the PT manifold. The origin is defined by the retro-insular end of the HG and the y-axis passes through the point on the posterior STG where the ramus begins. Automated labeling of GM in the STG is robust with L(1) distances between Bayesian and manual segmentation in the range 0.001-0.12 (n = 20). PT reconstruction is also robust with 90% of the vertices of the reconstructed PT within about 1 voxel (n = 20) from semiautomated contours. Finally, the reliability index (based on interrater intraclass correlation) for the surface area derived from repeated reconstructions is 0.96 for the left PT and 0.94 for the right PT, thus demonstrating the robustness of dynamic programming in defining a coordinate system on the PT. It provides a method with potential significance in the study of neuropsychiatric disorders.

Algorithms↗