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 55 records · Page 3Linked to original sources
PubMed1988

Smoothing noisy data using dynamic programming and generalized cross-validation.

Smoothing and differentiation of noisy data using spline functions requires the selection of an unknown smoothing parameter. The method of generalized cross-validation provides an excellent estimate of the smoothing parameter from the data itself even when the amount of noise associated with the data is unknown. In the present model only a single smoothing parameter must be obtained, but in a more general context the number may be larger. In an earlier work, smoothing of the data was accomplished by solving a minimization problem using the technique of dynamic programming. This paper shows how the computations required by generalized cross-validation can be performed as a simple extension of the dynamic programming formulas. The results of numerical experiments are also included.

Algorithms↗
PubMed2001

A biologically inspired neural network for dynamic programming.

An artificial neural network with a two-layer feedback topology and generalized recurrent neurons, for solving nonlinear discrete dynamic optimization problems, is developed. A direct method to assign the weights of neural networks is presented. The method is based on Bellmann's Optimality Principle and on the interchange of information which occurs during the synaptic chemical processing among neurons. The neural network based algorithm is an advantageous approach for dynamic programming due to the inherent parallelism of the neural networks; further it reduces the severity of computational problems that can occur in methods like conventional methods. Some illustrative application examples are presented to show how this approach works out including the shortest path and fuzzy decision making problems.

Algorithms↗
PubMed2006

Estimating linear cortical magnification in human primary visual cortex via dynamic programming.

Human primary visual cortex is organized retinotopically, with adjacent locations in cortex representing adjacent locations on the retina. The spatial sampling in cortex is highly nonuniform: the amount of cortex devoted to a unit area of retina decreases with increasing retinal eccentricity. This sampling property can be quantified by the linear cortical magnification factor, which is expressed in terms of millimeters of cortex per degree of visual angle. In this paper, we present a new method using dynamic programming and fMRI retinotopic eccentricity mapping to estimate the linear cortical magnification factor in human primary visual cortex (V1). We localized cortical activity while subjects viewed each of seven stationary contrast- reversing radial checkerboard rings of equal thickness that tiled the visual field from 1.62 to 12.96 degrees of eccentricity. Imaging data from all epochs of each ring were contrasted with data from fixation epochs on a subject-by-subject basis. The resulting t statistic maps were then superimposed on a local coordinate system constructed from the gray/white matter boundary surface of each individual subject's occipital lobe, separately for each ring. Smoothed maps of functional activity on the cortical surface were constructed using orthonormal bases of the Laplace-Beltrami operator that incorporate the geometry of the cortical surface. This allowed us to stably track the ridge of maximum activation due to each ring via dynamic programming optimization over all possible paths on the cortical surface. We estimated the linear cortical magnification factor by calculating geodesic distances between activation ridges on the cortical surface in a population of five normal subjects. The reliability of these estimates was assessed by comparing results based on data from one quadrant to those based on data from the full hemifield along with a split-half reliability analysis.

Brain Mapping↗
PubMed2006

A dynamic programming algorithm for binning microbial community profiles.

MOTIVATION: A number of community profiling approaches have been widely used to study the microbial community composition and its variations in environmental ecology. Automated Ribosomal Intergenic Spacer Analysis (ARISA) is one such technique. ARISA has been used to study microbial communities using 16S-23S rRNA intergenic spacer length heterogeneity at different times and places. Owing to errors in sampling, random mutations in PCR amplification, and probably mostly variations in readings from the equipment used to analyze fragment sizes, the data read directly from the fragment analyzer should not be used for down stream statistical analysis. No optimal data preprocessing methods are available. A commonly used approach is to bin the reading lengths of the 16S-23S intergenic spacer. We have developed a dynamic programming algorithm based binning method for ARISA data analysis which minimizes the overall differences between replicates from the same sampling location and time. RESULTS: In a test example from an ocean time series sampling program, data preprocessing identified several outliers which upon re-examination were found to be because of systematic errors. Clustering analysis of the ARISA from different times based on the dynamic programming algorithm binned data revealed important features of the biodiversity of the microbial communities.

Algorithms↗
PubMed1999

A dynamic programming algorithm for RNA structure prediction including pseudoknots.

We describe a dynamic programming algorithm for predicting optimal RNA secondary structure, including pseudoknots. The algorithm has a worst case complexity of O(N6) in time and O(N4) in storage. The description of the algorithm is complex, which led us to adopt a useful graphical representation (Feynman diagrams) borrowed from quantum field theory. We present an implementation of the algorithm that generates the optimal minimum energy structure for a single RNA sequence, using standard RNA folding thermodynamic parameters augmented by a few parameters describing the thermodynamic stability of pseudoknots. We demonstrate the properties of the algorithm by using it to predict structures for several small pseudoknotted and non-pseudoknotted RNAs. Although the time and memory demands of the algorithm are steep, we believe this is the first algorithm to be able to fold optimal (minimum energy) pseudoknotted RNAs with the accepted RNA thermodynamic model.

Algorithms↗
PubMed1993

[Analysis of handwriting by the dynamic programming matching].

We examined the temporal invariance hypothesis in handwriting, using dynamic programming (DP) matching algorithm. The DP matching algorithm was originally developed for the speech recognition to eliminate fluctuations of time axis caused by different speech rates. This algorithm can determine the optimal point-to-point correspondences (warping function) between the standard velocity pattern and different patterns. We found that this algorithm worked well for various velocity patterns, even when their total writing time was different from the standard pattern. Only 30 to 50 percent of handwriting movements showed temporal invariance. The writing movements which didn't show temporal invariance consisted of several sub-motor units. The borders between the units were not limited near the end of each letter. The results suggest that handwriting of a word does not show the temporal invariance and that it is executed by some discrete sub-motor units.

Adult↗
PubMed2000

Multiple protein sequence alignment using double-dynamic programming.

A method of multiple sequence alignment is described based on the double dynamic programming (DDP) algorithm previously used for treating structural constraints encountered in structure comparison and threading. Following these applications, the inconsistencies that emerge when trying to combine pair-wise alignments into a multiple alignment are reconciled by summing all the, possibly inconsistent, paths (low-level alignments) into a matrix which is then used to provide a final (high-level) alignment. This process is applied to all sequence pairs and the pair-wise results combined in a simple multiple sequence alignment program. From this alignment, further constraints are selected to bias the low-level alignments in the DDP algorithm and the process iterated. The results, however, showed that this overall iteration was not needed and one-pass gave results at least as good as the 'standard' progressive method of multiple sequence alignment. Further applications of the method are discussed.

Algorithms↗
PubMedDate not supplied

Q: a molecular dynamics program for free energy calculations and empirical valence bond simulations in biomolecular systems.

A new molecular dynamics program for free energy calculations in biomolecular systems is presented. It is principally designed for free energy perturbation simulations, empirical valence bond calculations, and binding affinity estimation by linear interaction energy methods. Evaluation of ligand-binding selectivity and free energy profiles for nucleophile activation in two protein tyrosine phosphatases as well as absolute binding affinity estimation for a lysine-binding protein are given as examples.

Algorithms↗
PubMed2004

CONDORR--CONstrained Dynamics of Rigid Residues: a molecular dynamics program for constrained molecules.

A computer program CONDORR (CONstrained Dynamics of Rigid Residues) was developed for molecular dynamics simulations of large and/or constrained molecular systems, particularly carbohydrates. CONDORR efficiently calculates molecular trajectories on the basis of 2D or 3D potential energy maps, and can generate such maps based on a simple force field. The simulations involve three translational and three rotational degrees of freedom for each rigid, asymmetrical residue in the model. Total energy and angular momentum are conserved when no stochastic or external forces are applied to the model, if the time step is kept sufficiently short. Application of Langevin dynamics allows longer time steps, providing efficient exploration of conformational space. The utility of CONDORR was demonstrated by application to a constrained polysaccharide model and to the calculation of residual dipolar couplings for a disaccharide. [Figure: see text]. Molecular models (bottom) are created by cloning rigid residue archetypes (top) and joining them together. As defined here, the archetypes AX, HM and BG respectively correspond to an alpha-D-Xyl p residue, a hydroxymethyl group, and a beta-D-Glc p residue lacking O6, H6a and H6b. Each archetype contains atoms (indicated by boxes) that can be shared with other archetypes to form a linked structure. For example, the glycosidic link between the two D-Glc p residues is established by specifying that O1 of the nonreducing beta-D-Glc p (BG) residue (2) is identical to O4 of the reducing Glc p (BG) residue (1). The coordinates of the two residues are adjusted so as to superimpose these two (nominally distinct) atoms. Flexible hydroxymethyl (HM) groups (3 and 4) are treated as separate residues, and the torsional angles (normally indicated by the symbol omega) that define their geometric relationships to the pyranosyl rings of the BG residues are specified as psi3 and psi4, respectively. The torsional angles phi3 and phi4, defined solely to maintain the orientation of the geminal H-atoms of the hydroxymethyl group, are not shown. (See text.). The illustrated trisaccharide is thus specified as a collection of 5 residues which are represented by 3 archetypes. Models of the disaccharide cellobiose (beta-D-Glc p-(1-->4)-D-Glc p) must include residues 1 and 2, but the hydroxymethyl groups (residues 3 and 4) can also be explicitly included in this model

Carbohydrates↗
PubMed1993

Defining topological equivalences in protein structures by means of a dynamic programming algorithm.

An automatic algorithm for defining topological equivalences in protein structures is presented. The algorithm is based on a dynamic programming technique and self-consistent scoring method. We have used it to align pairs of similar protein structures of several protein families and to identify recurrent structural domains in aspartic proteinase 2APR. Its ability to find suboptimal paths permits a thorough comparison of proteins at each level in the hierarchy of the protein structure: secondary structure, super-secondary structure, domain and entire globular structure. The algorithm has been extended to the structure alignment of ribonucleic acid and can be extended to the structure alignment of any linear polymer.

Algorithms↗
PubMed2005

Protein secondary structure prediction using dynamic programming.

In the present paper, we describe how a directed graph was constructed and then searched for the optimum path using a dynamic programming approach, based on the secondary structure propensity of the protein short sequence derived from a training data set. The protein secondary structure was thus predicted in this way. The average three-state accuracy of the algorithm used was 76.70%.

Algorithms↗
PubMed1996

Finding genes in DNA using decision trees and dynamic programming.

This study demonstrates the use of decision tree classifiers as the basis for a general gene-finding system. The system uses a dynamic programming algorithm that finds the optimal segmentation of a DNA sequence into coding and non-coding regions (exons and introns). The optimality property is dependent on a separate scoring function that takes a subsequence and assigns to it a score reflecting the probability that the sequence is an exon. In this study, the scoring functions were sets of decision trees and rules that were combined to give the probability estimate. Experimental results on a newly collected database of human DNA sequences are encouraging, and some new observations about the structure of classifiers for the gene-finding problem have emerged from this study. We also provide descriptions of a new probability chain model that produces very accurate filters to find donor and acceptor sites.

Algorithms↗
PubMed1981

Segmenting speech using dynamic programming.

Speech is modeled as a Markov chain. Scoring is developed to convert observations of the speech signal into estimated probabilities of the locations of segment boundaries. Dynamic programming is then used to compute a most-probable segmentation for the speech. The process automatically adjusts to speakers and incorporates a priori information in a probabilistic and systemic fashion. The performance of the algorithm appears to be state-of-the-art, independent of speaker.

Computers↗
PubMed2005

Reconfigurable systems for sequence alignment and for general dynamic programming.

Reconfigurable systolic arrays can be adapted to efficiently resolve a wide spectrum of computational problems; parallelism is naturally explored in systolic arrays and reconfigurability allows for redefinition of the interconnections and operations even during run time (dynamically). We present a reconfigurable systolic architecture that can be applied for the efficient treatment of several dynamic programming methods for resolving well-known problems, such as global and local sequence alignment, approximate string matching and longest common subsequence. The dynamicity of the reconfigurability was found to be useful for practical applications in the construction of sequence alignments. A VHDL (VHSIC hardware description language) version of this new architecture was implemented on an APEX FPGA (Field programmable gate array). It would be several magnitudes faster than the software algorithm alternatives.

Algorithms↗
PubMed1999

Protein structure comparison using iterated double dynamic programming.

A protein structure comparison method is described that allows the generation of large populations of high-scoring alternate alignments. This was achieved by incorporating a random element into an iterative double dynamic programming algorithm. The maximum scores from repeated comparisons of a pair of structures converged on a value that was taken as the global maximum. This lay 15% over the score obtained from the single fixed (unrandomized) calculation. The effect of the gap penalty was observed through the shift of the alignment populations, characterized by their alignment length and root-mean-square deviation (RMSD). The best (lowest RMSD) values found in these populations provided a base-line against which other methods were compared.

Protein Conformation↗
PubMed2006

STRUCTFAST: protein sequence remote homology detection and alignment using novel dynamic programming and profile-profile scoring.

STRUCTFAST is a novel profile-profile alignment algorithm capable of detecting weak similarities between protein sequences. The increased sensitivity and accuracy of the STRUCTFAST method are achieved through several unique features. First, the algorithm utilizes a novel dynamic programming engine capable of incorporating important information from a structural family directly into the alignment process. Second, the algorithm employs a rigorous analytical formula for profile-profile scoring to overcome the limitations of ad hoc scoring functions that require adjustable parameter training. Third, the algorithm employs Convergent Island Statistics (CIS) to compute the statistical significance of alignment scores independently for each pair of sequences. STRUCTFAST routinely produces alignments that meet or exceed the quality obtained by an expert human homology modeler, as evidenced by its performance in the latest CAFASP4 and CASP6 blind prediction benchmark experiments.

Algorithms↗
PubMed2005

Prediction of protein secondary structure based on residue pair types and conformational states using dynamic programming algorithm.

We have used a statistical approach for protein secondary structure prediction based on information theory and simultaneously taking into consideration pairwise residue types and conformational states. Since the prediction of residue secondary structure by one residue window sliding make ambiguity in state prediction, we used a dynamic programming algorithm to find the path with maximum score. A score system for residue pairs in particular conformations is derived for adjacent neighbors up to ten residue apart in sequence. The three state overall per-residue accuracy, Q3, of this method in a jackknife test with dataset created from PDBSELECT is more than 70%.

Algorithms↗
PubMed2000

A multiscale dynamic programming procedure for boundary detection in ultrasonic artery images.

Ultrasonic measurements of human carotid and femoral artery walls are conventionally obtained by manually tracing interfaces between tissue layers. The drawbacks of this method are the interobserver variability and inefficiency. In this paper, we present a new automated method which reduces these problems. By applying a multiscale dynamic programming (DP) algorithm, approximate vessel wall positions are first estimated in a coarse-scale image, which then guide the detection of the boundaries in a fine-scale image. In both cases, DP is used for finding a global optimum for a cost function. The cost function is a weighted sum of terms, in fuzzy expression forms, representing image features and geometrical characteristics of the vessel interfaces. The weights are adjusted by a training procedure using human expert tracings. Operator interventions, if needed, also take effect under the framework of global optimality. This reduces the amount of human intervention and, hence, variability due to subjectiveness. By incorporating human knowledge and experience, the algorithm becomes more robust. A thorough evaluation of the method in the clinical environment shows that interobserver variability is evidently decreased and so is the overall analysis time. We conclude that the automated procedure can replace the manual procedure and leads to an improved performance.

Carotid Artery, Common↗