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 181 records · Page 10Linked to original sources
PubMed1999

Two strategies for sequence comparison: profile-preprocessed and secondary structure-induced multiple alignment.

Multiple sequence alignment remains one of the most powerful tools for assessing sequence relateness and the identification of structurally and functionally important protein regions. In this work, two new techniques are introduced to increase the sensitivity of dynamic programming and to enable checks for alignment consistency: Profile-preprocessed and secondary structure-induced alignments. Both strategies are based upon the hierarchical dynamic programming technique and can be applied separately or used in combination. Alignments resulting from the strategies are shown in comparison with the multiple alignment methods CLUSTALX and MULTAL for distant sequence sets of the flavoxin and cupredoxin protein families.

Amino Acid Sequence↗
PubMed2005

A regularized and renormalized electrostatic coupling Hamiltonian for hybrid quantum-mechanical-molecular-mechanical calculations.

We describe a regularized and renormalized electrostatic coupling Hamiltonian for hybrid quantum-mechanical (QM)-molecular-mechanical (MM) calculations. To remedy the nonphysical QM/MM Coulomb interaction at short distances arising from a point electrostatic potential (ESP) charge of the MM atom and also to accommodate the effect of polarized MM atom in the coupling Hamiltonian, we propose a partial-wave expansion of the ESP charge and describe the effect of a s-wave expansion, extended over the covalent radius r(c), of the MM atom. The resulting potential describes that, at short distances, large scale cancellation of Coulomb interaction arises intrinsically from the localized expansion of the MM point charge and the potential self-consistently reduces to 1r(c) at zero distance providing a renormalization to the Coulomb energy near interatomic separations. Employing this renormalized Hamiltonian, we developed an interface between the Car-Parrinello molecular-dynamics program and the classical molecular-dynamics simulation program Groningen machine for chemical simulations. With this hybrid code we performed QM/MM calculations on water dimer, imidazole carbon monoxide (CO) complex, and imidazole-heme-CO complex with CO interacting with another imidazole. The QM/MM results are in excellent agreement with experimental data for the geometry of these complexes and other computational data found in literature.

Carbon Monoxide↗
PubMed1995

A divide and conquer approach to multiple alignment.

We present a report on work in progress on a divide and conquer approach to multiple alignment. The algorithm makes use of the costs calculated from applying the standard dynamic programming scheme to all pairs of sequences. The resulting cost matrices for pairwise alignment give rise to secondary matrices containing the additional costs imposed by fixing the path through the dynamic programming graph at a particular vertex. Such a constraint corresponds to a division of the problem obtained by slicing both sequences between two particular positions, and aligning the two sequences on the left and the two sequences on the right, charging for gaps introduced at the slicing point. To obtain an estimate for the additional cost imposed by forcing the multiple alignment through a particular vertex in the whole hypercube, we will take a (weighted) sum of secondary costs over all pairwise projections of the division of the problem, as defined by this vertex, that is, by slicing all sequences at the points suggested by the vertex. We then use that partition of every single sequence under consideration into two 'halfs' which imposes a minimal (weighted) sum of pairwise additional costs, making sure that one of the sequences is divided somewhere close to its midpoint. Hence, each iteration can cut the problem size in half. As the enumeration of all possible partitions may restrict this approach to small-size problems, we eliminate futile partitions, and organize their enumeration in a way that starts with the most promising ones.(ABSTRACT TRUNCATED AT 250 WORDS)

Algorithms↗
PubMed2003

PROSPECT II: protein structure prediction program for genome-scale applications.

A new method for fold recognition is developed and added to the general protein structure prediction package PROSPECT (http://compbio.ornl.gov/PROSPECT/). The new method (PROSPECT II) has four key features. (i) We have developed an efficient way to utilize the evolutionary information for evaluating the threading potentials including singleton and pairwise energies. (ii) We have developed a two-stage threading strategy: (a) threading using dynamic programming without considering the pairwise energy and (b) fold recognition considering all the energy terms, including the pairwise energy calculated from the dynamic programming threading alignments. (iii) We have developed a combined z-score scheme for fold recognition, which takes into consideration the z-scores of each energy term. (iv) Based on the z-scores, we have developed a confidence index, which measures the reliability of a prediction and a possible structure-function relationship based on a statistical analysis of a large data set consisting of threadings of 600 query proteins against the entire FSSP templates. Tests on several benchmark sets indicate that the evolutionary information and other new features of PROSPECT II greatly improve the alignment accuracy. We also demonstrate that the performance of PROSPECT II on fold recognition is significantly better than any other method available at all levels of similarity. Improvement in the sensitivity of the fold recognition, especially at the superfamily and fold levels, makes PROSPECT II a reliable and fully automated protein structure and function prediction program for genome-scale applications.

Algorithms↗
PubMed2003

A table-driven, full-sensitivity similarity search algorithm.

Searching a database for a local alignment to a query under a typical scoring scheme, such as PAM120 or BLOSUM62 with affine gap costs, is a computation that has resisted algorithmic improvement due to its basis in dynamic programming and the weak nature of the signals being searched for. In a query preprocessing step, a set of tables can be built that permit one to (a) eliminate a large fraction of the dynamic programming matrix from consideration and (b) to compute several steps of the remainder with a single table lookup. While this result is not an asymptotic improvement over the original Smith-Waterman algorithm, its complexity is characterized in terms of some sparse features of the matrix and it yields the fastest software implementation to date for such searches.

Algorithms↗
PubMed2000

GeneRAGE: a robust algorithm for sequence clustering and domain detection.

MOTIVATION: Efficient, accurate and automatic clustering of large protein sequence datasets, such as complete proteomes, into families, according to sequence similarity. Detection and correction of false positive and negative relationships with subsequent detection and resolution of multi-domain proteins. RESULTS: A new algorithm for the automatic clustering of protein sequence datasets has been developed. This algorithm represents all similarity relationships within the dataset in a binary matrix. Removal of false positives is achieved through subsequent symmetrification of the matrix using a Smith-Waterman dynamic programming alignment algorithm. Detection of multi-domain protein families and further false positive relationships within the symmetrical matrix is achieved through iterative processing of matrix elements with successive rounds of Smith-Waterman dynamic programming alignments. Recursive single-linkage clustering of the corrected matrix allows efficient and accurate family representation for each protein in the dataset. Initial clusters containing multi-domain families, are split into their constituent clusters using the information obtained by the multi-domain detection step. This algorithm can hence quickly and accurately cluster large protein datasets into families. Problems due to the presence of multi-domain proteins are minimized, allowing more precise clustering information to be obtained automatically. AVAILABILITY: GeneRAGE (version 1.0) executable binaries for most platforms may be obtained from the authors on request. The system is available to academic users free of charge under license.

Algorithms↗
PubMed2001

Effects on physical performance and pain from three dynamic training programs for women with work-related trapezius myalgia.

To compare training programs for women with trapezius myalgia regarding physical performance and pain, 102 women were randomized to strength, endurance, co-ordination and non-training groups. Before and after the intervention, static strength and dynamic muscular endurance in shoulder muscles were measured on a Cybex II dynamometer. Muscle activity in shoulder muscles was monitored via surface EMG. The signal amplitude ratio between the active and passive phase of repeated contractions indicated the ability to relax. Pain at present, pain in general and pain at worst were measured on visual analogue scales. After training, within group comparisons showed that the training groups rated less pain, and in the strength training group ratings of pain at worst differed from the non-training group. Using the non-training group as a reference, static strength increased in the strength and endurance training groups and muscular endurance in all training groups. The study indicates that regular exercises with strength, endurance or co-ordination training of neck/shoulder muscles might alleviate pain for women with work-related trapezius myalgia.

Adult↗
PubMed2002

Technological transfers from the European space programs: a dynamic view and comparison with other R&D projects.

This article presents the results and lessons learned from a series of studies carried out by the BETA research team (University Louis Pasteur of Strasbourg, France) to measure the spin-offs and technological transfers that resulted from European space programs. Beyond the quantitative results that are analyzed in detail, the article examines some of the main qualitative characteristics that shape the technology transfer process generated by these programs. In particular, it is demonstrated that three main characteristics have a significant impact on the technology transfer process: the nature of the technologies at stake (their degree of maturity, their degree of diversity, the extent to which they are generic or specific), the nature of the network of participants to the programs (the degree of mutual trust, the existence of absorptive capabilities) and the nature of the organizational structure of those firms which participated in the projects (their degree of decentralization, their degree of vertical integration). The article concludes by discussing how these lessons learned could be used to shape the procurement policies to be followed by space agencies in order to favor a high potential for technological transfers arising from future space projects.

Europe↗
PubMed1992

Efficient optimal decomposition of a sequence into disjoint regions, each matched to some template in an inventory.

Given an amino acid sequence, we discuss how to find efficiently an optimal set of disjoint regions (substrings, domains, modules, etc.), each of which can be matched to some element of a predefined inventory containing, for example, consensus sequences, protosequences, or protein family profiles. A two-stage approach to sequence decomposition, consisting of the detection of all acceptable matches followed by the construction of an optimal subset of compatible matches, leads to computational difficulties. When the problem is reformulated in terms of network comparisons, it can be solved in time quadratic in the length of the sequence and linear with the number of templates in the inventory, by a single pass of a dynamic programming algorithm. This method has the advantage that the criterion for acceptable matches can be relaxed without materially affecting computing time. Except under special conditions it is more efficient than previous segmentation methods based on dynamic programming.

Algorithms↗
PubMedDate not supplied

A greedy algorithm for aligning DNA sequences.

For aligning DNA sequences that differ only by sequencing errors, or by equivalent errors from other sources, a greedy algorithm can be much faster than traditional dynamic programming approaches and yet produce an alignment that is guaranteed to be theoretically optimal. We introduce a new greedy alignment algorithm with particularly good performance and show that it computes the same alignment as does a certain dynamic programming algorithm, while executing over 10 times faster on appropriate data. An implementation of this algorithm is currently used in a program that assembles the UniGene database at the National Center for Biotechnology Information.

Algorithms↗
PubMed1997

A new automated computerized analyzing system simplifies readings and reduces the variability in ultrasound measurement of intima-media thickness.

BACKGROUND AND PURPOSE: A computerized analyzing system with manual tracing of echo interfaces for measurement of intima-media thickness and lumen diameter in carotid and femoral arteries was previously developed by our research group and has been used for many years in several laboratories. However, manual measurements are not only time consuming, but the results from these readings are also dependent on training and subjective judgement. A further problem is the observed drift in measurements over time. A new computerized technique for automatic detection of echo interfaces was therefore developed. The aim of this study was to evaluate the new automated computerized analyzing system. METHODS: The new system is based on dynamic programming and includes optional interactive modification by the human operator. Local measurements of vessel echo intensity, intensity gradient, and boundary continuity are extracted by image analysis techniques and included as weighed terms in a cost function. The dynamic programming procedure is used for determining the optimal location of the vessel interfaces in a way that the cost function is minimized. RESULTS: With the new automated computerized analyzing system the measurement results were less dependent on the reader's experience, and the variability between readers was less compared with the old manual analyzing system. The measurements were also less time consuming. CONCLUSIONS: The new automated analyzing system will not only greatly increase the speed of measurements but also reduce the variability between readers. It should also reduce the variability between different laboratories if the same analyzing program is used. Furthermore, the new system will probably prevent the problem with drift in measurements over time.

Automation↗
PubMed1995

Minimizing the effect of period determination on the computation of amplitude perturbation in voice.

Current methods of computing amplitude perturbation present in human voices depend upon being able to accurately determine fundamental period. In this paper, two methods of estimating the amplitude perturbation present in human voices, which do not depend on accurate determination of the boundaries between fundamental periods, are described. In both of these methods, amplitude perturbation is computed as the variance of an ensemble of periods calculated after these periods have been aligned in time. In one method, time alignment is accomplished using zero-phase transformation. In the second method, an unconstrained dynamic programming procedure is used. The accuracy of estimating amplitude perturbation by these two methods is evaluated using synthetic and natural voice signals and is also compared with an estimation using zero-padding based time alignment. The unconstrained dynamic programming method is shown to provide accurate estimation of voice amplitude perturbation over a variety of signal conditions.

Female↗
PubMed2006

SVM-based detection of distant protein structural relationships using pairwise probabilistic suffix trees.

A new method based on probabilistic suffix trees (PSTs) is defined for pairwise comparison of distantly related protein sequences. The new definition is adopted in a discriminative framework for protein classification using pairwise sequence similarity scores in feature encoding. The framework uses support vector machines (SVMs) to separate structurally similar and dissimilar examples. The new discriminative system, which we call as SVM-PST, has been tested for SCOP family classification task, and compared with existing discriminative methods SVM-BLAST and SVM-Pairwise, which use BLAST similarity scores and dynamic-programming-based alignment scores, respectively. Results have shown that SVM-PST is more accurate than SVM-BLAST and competitive with SVM-Pairwise. In terms of computational efficiency, PST-based comparison is much better than dynamic-programming-based alignment. We also compared our results with the original family-based PST approach from which we were inspired. The present method provides a significantly better solution for protein classification in comparison with the family-based PST model.

Algorithms↗
PubMed1991

A simple method to generate non-trivial alternate alignments of protein sequences.

A major problem in sequence alignments based on the standard dynamic programming method is that the optimal path does not necessarily yield the best equivalencing of residues assessed by structural or functional criteria. An algorithm is presented that finds suboptimal alignments of protein sequences by a simple modification to the standard dynamic programming method. The standard pairwise weight matrix elements are modified in order to penalize, but not eliminate, the equivalencing of residues obtained from previous alignments. The algorithm thereby yields a limited set of alternate alignments that can differ considerably from the optimal. The approach is benchmarked on the alignments of immunoglobulin domains. Without a prior knowledge of the optimal choice of gap penalty, one of the suboptimal alignments is shown to be more accurate than the optimal.

Algorithms↗
PubMed2005

Inference of missing SNPs and information quantity measurements for haplotype blocks.

MOTIVATION: Missing data in genotyping single nucleotide polymorphism (SNP) spots are common. High-throughput genotyping methods usually have a high rate of missing data. For example, the published human chromosome 21 data by Patil et al. contains about 20% missing SNPs. Inferring missing SNPs using the haplotype block structure is promising but difficult because the haplotype block boundaries are not well defined. Here we propose a global algorithm to overcome this difficulty. RESULTS: First, we propose to use entropy as a measure of haplotype diversity. We show that the entropy measure combined with a dynamic programming algorithm produces better haplotype block partitions than other measures. Second, based on the entropy measure, we propose a two-step iterative partition-inference algorithm for the inference of missing SNPs. At the first step, we apply the dynamic programming algorithm to partition haplotypes into blocks. At the second step, we use an iterative process similar to the expectation-maximization algorithm to infer missing SNPs in each haplotype block so as to minimize the block entropy. The algorithm iterates these two steps until the total block entropy is minimized. We test our algorithm in several experimental data sets. The results show that the global approach significantly improves the accuracy of the inference. AVAILABILITY: Upon request.

Algorithms↗
PubMed1989

A tool for multiple sequence alignment.

Multiple sequence alignment can be a useful technique for studying molecular evolution and analyzing sequence-structure relationships. Until recently, it has been impractical to apply dynamic programming, the most widely accepted method for producing pairwise alignments, to comparisons of more than three sequences. We describe the design and application of a tool for multiple alignment of amino acid sequences that implements a new algorithm that greatly reduces the computational demands of dynamic programming. This tool is able to align in reasonable time as many as eight sequences the length of an average protein.

Algorithms↗
PubMed1990

Genetic algorithms and evolution.

The genetic algorithm (GA) as developed by Holland (1975, Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press) is an optimization technique based on natural selection. We use a modified version of this technique to investigate which aspects of natural selection make it an efficient search procedure. Our main modification to Holland's GA is the subdividing of the population into semi-isolated demes. We consider two examples. One is a fitness landscape with many local optima. The other is a model of singing in birds that has been previously analysed using dynamic programming. Both examples have epistatic interactions. In the first example we show that the GA can find the global optimum and that its success is improved by subdividing the population. In the second example we show that GAs can evolve to the optimal policy found by dynamic programming.

Algorithms↗
PubMed2006

Probabilistic fusion of stereo with color and contrast for bilayer segmentation.

This paper describes models and algorithms for the real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from color/contrast or from stereo alone is known to be error-prone. Here, color, contrast, and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves stereo in an extended six-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive color model that is learned on-the-fly and stereo disparities are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC), does not directly solve stereo. Instead, the stereo match likelihood is marginalized over disparities to evaluate foreground and background hypotheses and then fused with a contrast-sensitive color model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than either stereo or color/ contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.

Algorithms↗