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 577 records · Page 32Linked to original sources
PubMed1993

Improved alignment of weakly homologous protein sequences using structural information.

Protein sequence alignments can be improved when at least one of the proteins to be aligned has a known 3-D structure. In this work, geometrical constraints extracted from the target fold are evaluated in independent units that deal with complementary structural features. This information is used to set up mutation tables specific to the locally observed structural environments. The resulting partial evaluations are then combined linearly into a global function which is optimized by dynamic programming. Eventually, a score based on tertiary interactions can be used as a selection criterion to discriminate among a set of suboptimal alignments. The relevance of the scores given by each unit is tested on a representative set of protein families. Finally, a method for combining the different scores is described and its efficiency is evaluated on a few pairs of weakly homologous proteins.

Algorithms↗
PubMed1995

Protein fold recognition by threading: comparison of algorithms and analysis of results.

Optimal sequence threading can be used to recognize members of a library of protein folds which are closely related in 3-D structure to the native fold of an input test sequence, even when the test sequence is not significantly homologous to the sequence of any member of the fold library. The methods provide an alignment between the residues of the test sequence and the residue positions in a template fold. This alignment optimizes a score function, and the predicted fold is the highest scoring member of the library of folds. Most score functions contain a pairwise interaction energy term. This, coupled with the need to introduce gaps into the alignment, means that the optimization problem is NP hard. We report a comparison between two heuristic optimization algorithms used in the literature, double dynamic programming and an iterative algorithm based on the so-called frozen approximation. These are compared in terms of both the ranking of likely folds and the quality of the alignment produced.

Algorithms↗
PubMed1996

Pairwise iterative superposition of distantly related proteins and assessment of the significance of 3-D structural similarity.

A challenge lies in identifying distant protein 3-D structural similarity by rigid-body superposition. The most common measure of structural similarity is r.m.s. distance (r.m.s.d.) between topologically equivalent residues, and most automated methods of protein modelling rely on the assembly of rigid fragments from known 3-D structures. A fast method of improving the definition of a common protein fold by superposition, especially for distant relationships, is described. The definition of topological equivalence by the standard dynamic programming sequence alignment algorithm is extended by refining the entire structure alignment (not just those equivalenced residues within a given cut-off distance) and determining whether the alignment can be continued at the termini. The most appropriate distance-based definition of topological equivalence for a given comparison is identified. Despite the fact that hitherto the distant similarity between the globin fold and colicin A has not been recognized directly by rigid-body superposition, this new approach defines more equivalent residues with a lower r.m.s.d. between them than that obtained by the superposition of equivalences identified by a more elaborate method. A previous distance metric of 3-D structural similarity derived from rigid-body superposition has been extended to the assessment of superpositions where topological equivalences have been determined by methods other than rigid-body ones.

Algorithms↗
PubMed2003

Protein fold comparison by the alignment of topological strings.

Using the definitions of protein folds encoded in a text string, a dynamic programming algorithm was devised to compare these and identify their largest common substructure and calculate the distance (in terms of the number of edit operations) that this lay from each structure. This provided a metric on which the folds were clustered into a 'phylogenetic' tree. This construction differs from previous automatic structure clustering algorithms as it has explicit representation of the structures at 'ancestral' branching nodes, even when these have no corresponding known structure. The resulting tree was compared with that compiled by an 'expert' in the field and while there was broad agreement, differences were found that resulted from differing degrees of emphasis being placed on the types of operations that can be used to transform structures. Some concluding speculations on the relationship of such trees to the evolutionary history and folding of the proteins are advanced.

Computational Biology↗
PubMed2006

Variable gap penalty for protein sequence-structure alignment.

The penalty for inserting gaps into an alignment between two protein sequences is a major determinant of the alignment accuracy. Here, we present an algorithm for finding a globally optimal alignment by dynamic programming that can use a variable gap penalty (VGP) function of any form. We also describe a specific function that depends on the structural context of an insertion or deletion. It penalizes gaps that are introduced within regions of regular secondary structure, buried regions, straight segments and also between two spatially distant residues. The parameters of the penalty function were optimized on a set of 240 sequence pairs of known structure, spanning the sequence identity range of 20-40%. We then tested the algorithm on another set of 238 sequence pairs of known structures. The use of the VGP function increases the number of correctly aligned residues from 81.0 to 84.5% in comparison with the optimized affine gap penalty function; this difference is statistically significant according to Student's t-test. We estimate that the new algorithm allows us to produce comparative models with an additional approximately 7 million accurately modeled residues in the approximately 1.1 million proteins that are detectably related to a known structure.

Algorithms↗
PubMedDate not supplied

Automated measurement of volume flow in the ascending aorta using MR velocity maps: evaluation of inter- and intraobserver variability in healthy volunteers.

PURPOSE: An automated contour detection algorithm was developed for the objective and reproducible quantitative analysis of velocity-encoded MR studies of the ascending aorta. METHOD: The only user interaction required is the manual definition of a center point inside the cross-section of the aorta in one of the available images. The automated contour detection algorithm detects an initial model contour in this image and subsequently corrects for motion and deformation of the aortic cross-section in each of the acquired images over the complete cardiac cycle using dynamic programming techniques. Integrating the flow velocity values for each pixel within the detected contour results in an instantaneous flow value. Next, by integrating the instantaneous flow values for each acquired phase over the complete cardiac cycle, left ventricular stroke volume measurement could be obtained. The results of the automated method were compared with results derived from manually traced contours in MR studies from 11 healthy volunteers. RESULTS: An excellent agreement in stroke volume measurements was observed: signed difference 0.61+/-1.15%. Inter- and intraobserver variabilities were <2% for both manual and automated image analysis methods. Manual tracing of contours required on the order of 10 min; the analysis time for automated contour detection was <6 s/study. CONCLUSION: The present contour detection allows fast and reliable left ventricular stroke volume measurements from aortic flow studies using velocity-encoded MR studies in healthy volunteers. Further study is required to assess the accuracy and reproducibility of the algorithm in patients with aortic and aortic valve disease.

Adult↗
PubMed2004

Evolution of mammals: lactation helps mothers to cope with unreliable food supplies.

Lactation is a ubiquitous feature of mammalian reproduction. Because lactating females can draw on their nutrient reserves for milk production, it offers mothers and their dependent young independence from fluctuations in their food supplies. However, converting food to reserves and milk is relatively inefficient at delivering nutrients to offspring. We use dynamic programming to contrast the performance of mothers that provision dependent, refuge-bound offspring optimally from their nutrient reserves with otherwise equivalent mothers that do so directly from the food they find. In this way, we demonstrate formally that the selective advantage to lactating mothers, who can provision--at a cost--without having found food recently, can be substantial with uncertain food supplies and few opportunities for future reproduction under a wide range of circumstances. Hence, it is likely that unreliability associated with the lifestyles of the small, primitive mammal-like reptiles that evolved extended maternal care, selected for fully-developed milk production and consumption, prompting the evolution of true mammals. Moreover, this work suggests that selection for coping with unreliable food access during provisioning may underlie key life-history differences between birds and mammals because the mass constraints imposed by flight restrict the level of reserves that mothers can carry and provision from.

Animal Nutritional Physiological Phenomena↗
PubMed2005

How optimal life history changes with the community size-spectrum.

This paper derives optimal life histories for fishes or other animals in relation to the size spectrum of the ecological community in which they are both predators and prey. Assuming log-linear size-spectra and well known scaling laws for feeding and mortality, we first construct the energetics of the individual. From these we find, using dynamic programming, the optimal allocation of energy between growth and reproduction as well as the trade-off between offspring size and numbers. Optimal strategies were found to be strongly dependent on size spectrum slope. For steep size spectra (numbers declining rapidly with size), determinate growth was optimal and allocation to somatic growth increased rapidly with increasing slope. However, restricting reproduction to a fixed mating season changed optimal allocations to give indeterminate growth approximating a von Bertalanffy trajectory. The optimal offspring size was as small as possible given other restrictions such as newborn starvation mortality. For shallow size spectra, finite optimal maturity size required a decline in fitness for large size or age. All the results are compared with observed size spectra of fish communities to show their consistency and relevance.

Animals↗
PubMed2002

A theoretical analysis of the energetic costs and consequences of parental care decisions.

Should a parent care for its young or abandon them before they reach independence? We consider parental care behaviour as an adaptive decision, involving trade-offs between current and future reproduction. The condition of the parent is expected to influence these trade-offs. Using a dynamic programming model we explore how changes in the levels of energetic reserves, and time in the season, determine changes in parental care decisions. The novel feature of our model is that we have included the possibility of remating within the current breeding season in a consistent manner by explicitly modelling the behaviour of unmated animals. We show that there may be several fluctuations in the average duration of care during the breeding season. We also show that, because of the dependence of parental care behaviour on both the condition of the parent and time during the breeding season, changing some of the costs of care may increase the duration of care during one part of the season and decrease it at another. The model also shows that the conditions prevailing for animals with dependent offspring can affect the way in which an unmated animal behaves. For example, the behaviour of unmated animals may change to compensate (partly) for increases in the costs of raising offspring, which are produced at a later date (for example, by increasing the duration of foraging between breeding attempts). Overall, the model provides a good framework for understanding how various ecological and life-history variables should influence parental care behaviour during a breeding season.

Age Factors↗
PubMed2025

Investigating milk-derived extracellular vesicles as mediators of maternal stress and environmental intervention.

Parental communication signals are transmitted through nursing and critically shape neurodevelopmental trajectories. Mirroring some well characterized effects of gestational challenges in rodents, maternal immune activation (MIA) during the lactational period disrupts maternal physiology, decreases lipid content, and is associated with adverse neurobehavioral outcomes in offspring. This occurs without MIA significantly affecting maternal care. While gestational MIA models are responsive to environmental interventions, which beneficially alter maternal milk composition and associated offspring outcomes, the bioactive mediators in milk underlying resilience remain poorly understood. Milk-derived extracellular vesicles (MEVs) transport and deposit biologically active cargo, including microRNAs (miRNAs) that induce post-translational regulation of candidate mRNA in the nursing offspring's tissues and cells. Using a rat model, we show that lactational MIA alters MEV-miRNA cargo and the expression of hippocampal miRNAs in offspring. Several miRNAs in MEVs were also found in the hippocampus of matching offspring. Remarkably, the miRNA changes in MEVs and the neonatal hippocampus were rescued when dams were raised in an enriched environment, suggesting environmental enrichment protected from the effects of MIA. This was supported by the behavioral phenotype. RNA-seq of adult offspring hippocampus showed long-term transcriptional changes associated with the gene targets of early-life regulated miRNAs. Our results position MEV-miRNA as dynamic programming signals by which maternal experience is communicated to offspring, encoding both stress-induced and protective cues that influence development. This suggests that breastfeeding interventions can regulate the genetic cargo of the milk, programming the life of developing infants.

Journal Article↗
PubMed2004

Haplotype block partitioning and tag SNP selection using genotype data and their applications to association studies.

Recent studies have revealed that linkage disequilibrium (LD) patterns vary across the human genome with some regions of high LD interspersed by regions of low LD. A small fraction of SNPs (tag SNPs) is sufficient to capture most of the haplotype structure of the human genome. In this paper, we develop a method to partition haplotypes into blocks and to identify tag SNPs based on genotype data by combining a dynamic programming algorithm for haplotype block partitioning and tag SNP selection based on haplotype data with a variation of the expectation maximization (EM) algorithm for haplotype inference. We assess the effects of using either haplotype or genotype data in haplotype block identification and tag SNP selection as a function of several factors, including sample size, density or number of SNPs studied, allele frequencies, fraction of missing data, and genotyping error rate, using extensive simulations. We find that a modest number of haplotype or genotype samples will result in consistent block partitions and tag SNP selection. The power of association studies based on tag SNPs using genotype data is similar to that using haplotype data.

Algorithms↗
PubMed2026

k-mer-based Upstream Preprocessing of long reads for Isoform Discovery.

Eukaryotic genes can encode multiple protein isoforms based on alternative splicing of their transcribed regions. Most modern novel isoform discovery methods function by identifying and assembling exon splice junctions from an RNA-seq sample. However, splice junctions can only be accurately annotated with time-intensive dynamic programming alignment. This manuscript introduces KuPID, a method for preprocessing long RNA-seq reads with the goal of better identifying novel isoform transcripts. KuPID utilizes k-mer sketching as a prefilter to quickly pseudo-align reads to known reference isoforms. Full alignment need only then be applied to reads that are most relevant to isoform discovery. Not only does KuPID speed up the discovery pipeline, it also increases downstream accuracy by filtering out extraneous reads. KuPID preprocessing simultaneously increases the f1 accuracy of isoform discovery pipelines by up to 11.6 points while decreasing the runtime by a factor of 2-3&#xd7;;. An optional mode permits a KuPID sample to be paired with both isoform discovery and transcript quantification.

Journal Article↗
PubMed2005

Design optimization methods for genomic DNA tiling arrays.

A recent development in microarray research entails the unbiased coverage, or tiling, of genomic DNA for the large-scale identification of transcribed sequences and regulatory elements. A central issue in designing tiling arrays is that of arriving at a single-copy tile path, as significant sequence cross-hybridization can result from the presence of non-unique probes on the array. Due to the fragmentation of genomic DNA caused by the widespread distribution of repetitive elements, the problem of obtaining adequate sequence coverage increases with the sizes of subsequence tiles that are to be included in the design. This becomes increasingly problematic when considering complex eukaryotic genomes that contain many thousands of interspersed repeats. The general problem of sequence tiling can be framed as finding an optimal partitioning of non-repetitive subsequences over a prescribed range of tile sizes, on a DNA sequence comprising repetitive and non-repetitive regions. Exact solutions to the tiling problem become computationally infeasible when applied to large genomes, but successive optimizations are developed that allow their practical implementation. These include an efficient method for determining the degree of similarity of many oligonucleotide sequences over large genomes, and two algorithms for finding an optimal tile path composed of longer sequence tiles. The first algorithm, a dynamic programming approach, finds an optimal tiling in linear time and space; the second applies a heuristic search to reduce the space complexity to a constant requirement. A Web resource has also been developed, accessible at http://tiling.gersteinlab.org, to generate optimal tile paths from user-provided DNA sequences.

Algorithms↗
PubMed1999

Thermodynamic framework for discrete optimal control in multiphase flow systems.

Bellman's method of dynamic programming is used to synthesize diverse optimization approaches to active (work producing) and inactive (entropy generating) multiphase flow systems. Thermal machines, optimally controlled unit operations, nonlinear heat conduction, spontaneous relaxation processes, and self-propagating wave fronts are all shown to satisfy a discrete Hamilton-Jacobi-Bellman equation and a corresponding discrete optimization algorithm of Pontryagin's type, with the maximum principle for a Hamiltonian. The extremal structures are always canonical. A common unifying criterion is set for all considered systems, which is the criterion of a minimum generated entropy. It is shown that constraints can modify the entropy functionals in a different way for each group of the processes considered; thus the resulting structures of these functionals may differ significantly. Practical conclusions are formulated regarding the energy savings and energy policy in optimally controlled systems.

Journal Article↗
PubMed2005

Dependence of RNA secondary structure on the energy model.

We analyze a microscopic RNA model, which includes two widely used models as limiting cases; namely, it contains terms for bond as well as for stacking energies. We numerically investigate possible changes in the qualitative and quantitative behavior while going from one model to the other; in particular, we test whether a transition occurs when continuously moving from one model to the other. For this we calculate various thermodynamic quantities, at both zero temperature and finite temperatures. All calculations can be done efficiently in polynomial time by a dynamic programming algorithm. We do not find a sign for the transition between the models, but the critical exponent nu of the correlation length, describing the phase transition in all models to an ordered low-temperature phase, seems to depend continuously on the model. Finally, we apply the epsilon -coupling method to study low-energy excitations. The exponent theta describing the energy scaling of the excitations seems to depend not much on the energy model.

Algorithms↗
PubMed1990

Temporal feature extraction and clustering analysis of electromyographic linear envelopes in gait studies.

A technique for automatically clustering linear envelopes of the EMG during gait has been developed which uses a temporal feature representation and a maximum peak matching scheme. This new technique provides a viable way to define compact and meaningful EMG waveform features. The envelope matching is performed by dynamic programming, providing qualitatively the largest numbers of matched peaks and quantitatively a minimum distance measurement. The resulting averaged EMG profiles have low statistical variation and can serve as templates for EMG comparison and further classification.

Algorithms↗
PubMed1997

Graphical shape templates for automatic anatomy detection with applications to MRI brain scans.

A new method of model registration is proposed using graphical templates. A decomposable graph of landmarks is chosen in the template image. All possible candidates for these landmarks are found in the data image using robust relational local operators. A dynamic programming algorithm on the template graph finds the optimal match to a subset of the candidate points in polynomial time. This combination--local operators to describe points of interest/landmarks and a graph to describe their geometric arrangement in the plane--yields fast and precise matches of the model to the data with no initialization required. In addition, it provides a generic tool box for modeling shape in a variety of applications. This methodology is applied in the context of T2-weighted magnetic resonance (MR) axial and sagittal images of the brain to identify specific anatomies.

Algorithms↗
PubMed1997

Deformable 2-D template matching using orthogonal curves.

In this paper a new formulation of the two-dimensional (2-D) deformable template matching problem is proposed. It uses a lower-dimensional search space than conventional methods by precomputing extensions of the deformable template along orthogonal curves. The reduction in search space allows the use of dynamic programming to obtain globally optimal solutions and reduces the sensitivity of the algorithm to initial placement of the template. Further, the technique guarantees that the result is a curve which does not collapse to a point in the absence of strong image gradients and is always nonself intersecting. Examples of the use of the technique on real-world images and in simulations at low signal-to-noise ratios (SNR's) are also provided.

Algorithms↗