PubMed Health⌕ Search

SEARCH · PubMed Health

Results for “Dynamic Programming”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original 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
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↗
PubMed1992

Dynamic programming algorithms for restriction map comparison.

For most sequence comparison problems there is a corresponding map comparison algorithm. While map data may appear to be incompatible with dynamic programming, we show in this paper that the rigor and efficiency of dynamic programming algorithms carry over to the map comparison algorithms. We present algorithms for restriction map comparison that deal with two types of map errors: (i) closely spaced sites for different enzymes can be ordered incorrectly, and (ii) closely spaced sites for the same enzyme can be mapped as a single site. The new algorithms are a natural extension of a previous map comparison model. Dynamic programming algorithms for computing optimal global and local alignments under the new model are described. The new algorithms take about the same order of time as previous map comparison algorithms. Programs implementing some of the new algorithms are used to find similar regions within the Escherichia coli restriction map of Kohara et al.

Algorithms↗
PubMed1992

A contig assembly program based on sensitive detection of fragment overlaps.

An effective computer program for assembling DNA fragments, the contig assembly program (CAP), has been developed. In the CAP program, a filter is used to eliminate quickly fragment pairs that could not possibly overlap, a dynamic programming algorithm is applied to compute the maximal-scoring overlapping alignment between each remaining pair of fragments, and a simple greedy approach is employed to assemble fragments in order of alignment scores. To identify the true fragment overlaps, the dynamic programming algorithm uses specially chosen sets of alignment parameters to tolerate sequencing errors and to penalize "mutational" changes between different copies of a repetitive sequence. The performance tests of the program on fragment data from genomic sequencing projects produced satisfactory results. The CAP program is efficient in computer time and memory; it took about 4 h to assemble a set of 1015 fragments into long contigs on a Sun workstation.

Algorithms↗
PubMed2026

Exhausted CD8+ T cell fate is programmed by dynamic CTCF-mediated enhancer activation and invariant CTCF-imposed barriers.

Exhausted CD8+ T (TEX) cells undergo extensive genome reorganization during differentiation, yet the drivers of this process remain elusive. Here we show that CTCF programmed CD8+ TEX cell fates through two distinct modes of action. CTCF acquired de novo binding sites and concordantly induced open chromatin in early CD8+ TEX cells responding to chronic viral infection. The dynamic CTCF binding activated enhancers and promoted chromatin looping. Consequently, genetic ablation of CTCF diminished chromatin accessibility and interaction strength, impairing CD8+ TEX cell proliferation, effector function and bioenergetic mobilization. Conversely, invariant CTCF binding acted as essential chromatin barriers, and loss of CTCF disrupted insulation and caused aberrant chromatin self-association and undue RNA polymerase II pausing, leading to excessive activation of exhaustion- and stemness-linked genes. Thus, CTCF balanced CD8+ TEX cell differentiation by gaining dynamic binding to induce cytotoxicity and sustain metabolic fitness, while its invariant binding compartmentalized exhaustion and stemness program genes to prevent their overexuberant activation.

CCCTC-Binding Factor↗
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↗
PubMed1992

Evolution of an automated ST-segment analysis program for dynamic real-time, noninvasive detection of coronary occlusion and reperfusion.

Patients in whom early and stable reperfusion through the infarct artery fails after thrombolytic treatment might benefit from further revascularization therapy. A reliable noninvasive technique able to detect both reperfusion and reocclusion would be useful to test this hypothesis. However, no such technique presently exists. ST-segment recovery analysis using continuous digital 12-lead ST monitoring has been shown to be an accurate predictor of infarct artery patency in real time. This method was dependent on a trained clinician's analysis of the recordings on a personal computer. For optimal bedside application, salient principles of this ST-segment recovery analysis were converted into algorithms and built into the ST monitor software. The essentials of these algorithms are described in this report.

Electrocardiography↗
PubMed2026

Episode clustering in phylogenetic networks.

MOTIVATION: The classical duplication episode clustering (EC) model introduced by Guigó et al. in the 1990s provides a foundational approach for inferring genomic duplication events crucial to understanding genome evolution. This model clusters single gene duplications from a collection of gene trees at locations in the species tree to minimize the total number of such locations, called duplication episodes. However, it does not capture reticulate evolutionary histories. RESULTS: Here, we introduce NetEC, a novel extension of this problem to phylogenetic networks. To solve NetEC, we first develop a polynomial-time dynamic programming (DP) algorithm for testing whether a given set of network nodes can serve as episode locations. We then propose a main inference algorithm that utilizes this DP component to optimize the episode count; while the feasibility test runs in polynomial time, the full optimization has exponential worst-case complexity, and an optional heuristic mode is provided for larger instances. We also propose an extended episode analysis procedure that identifies additional genomic duplication candidates below reticulation nodes, complementing the main algorithm by resolving potential upward clustering of duplications induced by reticulation. We evaluate our method on simulated data and on an empirical Pandanales dataset comprising over 29 000 gene trees, demonstrating exact and accurate inference of genomic duplication events even in the presence of multiple reticulations. AVAILABILITY AND IMPLEMENTATION: All experiments were conducted using the NetEC tool (https://github.com/ppgorecki/netec), with all input data, scripts, and parameter settings for reproduction available in the same repository.

Phylogeny↗
PubMed2026

Singletrack: an algorithm for improving memory consumption and performance of gap-affine sequence alignment.

MOTIVATION: Advances in DNA sequencing have outpaced advances in computation, making sequence alignment a major bottleneck in genome data analyses. Classical dynamic programming (DP) algorithms are particularly memory-intensive, especially when computing gap-affine and dual gap-affine alignments. Existing strategies to reduce memory consumption often sacrifice speed or alignment accuracy. RESULTS: We present Singletrack, an efficient algorithm for backtrace gap-affine and dual gap-affine alignments that requires storing a single DP matrix while preserving optimal alignment results. Compared to classical DP algorithms, Singletrack removes the need to store additional matrices (i.e. 2 for gap-affine and 4 for dual gap-affine), significantly reducing memory consumption and, in turn, reducing pressure on the memory hierarchy and improving overall performance. Most importantly, Singletrack is a general backtrace method compatible with state-of-the-art DP-based algorithms and heuristics, such as the Suzuki-Kasahara (SK) and the Wavefront Alignment (WFA) algorithms. We demonstrate that Singletrack reduces memory consumption for both SK and WFA algorithms, lowering SK usage by 2× and 4× and WFA usage by 3× and 5× for gap-affine and dual gap-affine alignments, respectively. Moreover, replacing KSW2's memory-reduction technique with Singletrack accelerates its SK implementation by up to 1.4× at the cost of doubling memory consumption, while Singletrack increases the performance of the WFA implementation in WFA2-lib by 1.2-2.1×. Compared to the efficient linear-memory BiWFA algorithm, the Singletrack-accelerated version of WFA trades a practical increase in memory usage for up to 5.2× higher performance. AVAILABILITY AND IMPLEMENTATION: The Singletrack implementations presented in this work are available on Zenodo (DOI: 10.5281/zenodo.18770585) and GitHub (https://github.com/LorienLV/singletrack).

Algorithms↗
PubMed1976

Computer-aided anaesthesia administration.

Certain repetitive tasks of the anaesthesiologist are studied and modelled for automatic processing. These analyses make it possible for optimal control procedures to be programmed and administered by less trained anaesthesia professionals. A dynamic programming model is developed and validated with real data collected from several hospitals in the Cleveland, Ohio, area. By conjunctively monitoring certain transients in the anaesthesia administration process, the scarce supply of anaesthesiology manpower can be more efficiently deployed.

Anesthesia↗
PubMed1978

Dynamic scintigraphy: calculatiion and imaging of regional distribution of quantitative parameters.

The theory and general method of calculation of the parametric (functional) images at dynamic studies is described briefly. This method is illustrated by a general program DYNAM. PARAM. PRESENT. created for Clincom apparatus. Moreover, the selection of parameters and algorithms for calculation, the problems associated with the filtration of data, the correction for dead time and for non-homogeneity are discussed. In addition to the general method, there are presented here the possible ways of application of the simplified methods of construction of the parametric images by means of algebraic operations between images in special cases. Some aspects of that method are completed by examples of practical parametric images of some organs.

Computers↗
PubMed1992

A graphics program for the analysis and display of molecular dynamics trajectories.

The program SCARECROW has been developed to help the molecular modeler to analyze and display the very big and complex data files produced by molecular dynamics programs. The molecular graphics program SCARECROW is written to support the display, animation, and extensive analysis of molecular dynamics trajectories. Using the macro language it is easy to make scripts for video animation and for the automated display and analysis of time series. Extensive coloring and atom selection commands are included to help the user to focus on relevant regions of the molecule. Time series can be produced and viewed on the screen or transferred to other programs.

Chemical Phenomena↗
PubMed1992

Distal pocket residues affect picosecond ligand recombination in myoglobin. An experimental and molecular dynamics study of position 29 mutants.

Time courses for intramolecular NO and O2 recombination to native and three position 29 mutants of sperm whale myoglobins were measured after laser photolysis on picosecond and nanosecond time scales. The rates for the first phase of NO recombination were 1.8, 2.5, 29, and > or = 100 ns-1 for Ala29, Val29, Leu29 (native), and Phe29 myoglobin, respectively, at room temperature. This order is not correlated with the overall association rate constants for NO binding which were all in the range 20-50 x 10(6) M-1 s-1 and is the opposite of that observed for the rate constants for the overall thermal dissociation of NO which were 5.0, 2.8, 0.98, and 0.21 x 10(-4) s-1 for Ala29, Val29, Leu29 (native), and Phe29 myoglobin, respectively, at 20 degrees C. This inverse correlation suggests that photo- and thermally dissociated ligand molecules experience similar kinetic and equilibrium barriers to rebinding. The larger side chains of Leu29 and Phe29 inhibit rapid movement of the ligand away from the iron atom facilitating geminate recombination. The smaller side chains of Val29 and Ala29 increase the space available to the ligand, decreasing the rate of geminate recombination and enhancing complete dissociation. Diffusion of NO in the distal pocket of myoglobin was simulated using a variant of the molecular dynamics program CHARMM that includes the locally enhanced sampling protocol (Elber, R., and Karplus, M. (1991) J. Am. Chem. Soc. 112, 9161-9175; Roitberg, A., and Elber, R. (1991) J. Chem. Phys. 95, 9277-9287) and the x-ray structures of Carver et al. (Carver, T. E., Brantley, R. E., Jr., Singleton, E. W., Arduini, R. M., Quillin, M. L., Phillips, G. N., Jr., and Olson, J. S. (1992) J. Biol. Chem. 267, 14443-14450). Both accelerated (5,000 K) and room temperature ligands were used, and comparisons were made between simulations with a complete hydration shell surrounding the protein and those with only eight water molecules near the distal histidine. Photodissociated ligands initially move away from the heme plane, past Leu29, and toward Leu32, Phe33, Ile107, and Ile111. These theoretical results confirm that a complete description of picosecond ligand recombination must include the dynamics of ligand movement in the distal portion of the heme pocket.

Animals↗
PubMed2025

Pioneer in Molecular Biology: Conformational Ensembles in Molecular Recognition, Allostery, and Cell Function.

In 1978, for my PhD, I developed the efficient O(n3) dynamic programming algorithm for the-then open problem of RNA secondary structure prediction. This algorithm, now dubbed the "Nussinov algorithm", "Nussinov plots", and "Nussinov diagrams", is still taught across Europe and the U.S. As sequences started coming out in the 1980s, I started seeking genome-encoded functional signals, later becoming a bioinformatics trend. In the early 1990s I transited to proteins, co-developing a powerful computer vision-based docking algorithm. In the late 1990s, I proposed the foundational role of conformational ensembles in molecular recognition and allostery. At the time, conformational ensembles and free energy landscapes were viewed as physical properties of proteins but were not associated with function. The classical view of molecular recognition and binding was based on only two conformations captured by crystallography: open and closed. I proposed that all conformational states preexist. Proteins always have not one folded form-nor two-but many folded forms. Thus, rather than inducing fit, binding can work by shifting the ensembles between states, and this shifting, or redistributing the ensembles to maintain equilibrium, is the origin of the allosteric effect and protein, thus cell, function. This transformative paradigm impacted community views in allosteric drug design, catalysis, and regulation. Dynamic conformational ensemble shifts are now acknowledged as the origin of recognition, allostery, and signaling, underscoring that conformational ensembles-not proteins-are the workhorses of the cell, pioneering the fundamental idea that dynamic ensembles are the driving force behind cellular processes. Nussinov was recognized as pioneer in molecular biology by JMB.

Molecular Biology↗
PubMed1992

Optimizing model: insemination, replacement, seasonal production, and cash flow.

Dynamic programming to solve the Markov decision process problem of optimal insemination and replacement decisions was adapted to address large dairy herd management decision problems in the US. Expected net present values of cow states (151,200) were used to determine the optimal policy. States were specified by class of parity (n = 12), production level (n = 15), month of calving (n = 12), month of lactation (n = 16), and days open (n = 7). Methodology optimized decisions based on net present value of an individual cow and all replacements over a 20-yr decision horizon. Length of decision horizon was chosen to ensure that optimal policies were determined for an infinite planning horizon. Optimization took 286 s of central processing unit time. The final probability transition matrix was determined, in part, by the optimal policy. It was estimated iteratively to determine post-optimization steady state herd structure, milk production, replacement, feed inputs and costs, and resulting cash flow on a calendar month and annual basis if optimal policies were implemented. Implementation of the model included seasonal effects on lactation curve shapes, estrus detection rates, pregnancy rates, milk prices, replacement costs, cull prices, and genetic progress. Other inputs included calf values, values of dietary TDN and CP per kilogram, and discount rate. Stochastic elements included conception (and, thus, subsequent freshening), cow milk production level within herd, and survival. Validation of optimized solutions was by separate simulation model, which implemented policies on a simulated herd and also described herd dynamics during transition to optimized structure.

Animals↗
PubMed1992

Solution structures of cyclic and dicyclic analogues of growth hormone releasing factor as determined by two-dimensional NMR and CD spectroscopies and constrained molecular dynamics.

Solution structures were determined for a linear analogue of growth hormone releasing factor (GRF), and cyclic and dicyclic analogues in which the side chains of aspartyl and lysyl residues spaced at positions i-(i + 4) were joined to form a lactam. The four analogues were [Ala15]-GRF-(1-29)-NH2 and its cyclo8-12, cyclo21-25, and dicyclo8-12;21-25 derivatives. The peptides were studied in two solvent systems: 75% methanol/25% water at pH 6.0; and 100% water at pH 3.0. CD spectroscopy was used to assess the overall alpha-helical content. Nuclear magnetic resonance spectroscopy was used to determine the structures in more detail. Nearly complete proton resonance assignments were made for each of the peptides, in both solvents. Nuclear Overhauser effects were converted into distance constraints and applied in the molecular dynamics program CHARMM to evaluate the range of low-energy structures that satisfied the nmr data. In 75% methanol, all of the peptides are comprised of a single alpha-helical segment with fraying of one to three residues at each end. The linear analogue has a tendency to kink. In water, the analogues have two helical segments with flexible regions between them and at the termini of the peptides. The linear analogue is helical at residues 7-14 and 21-28. In the cyclo8-12 analogue, the N-terminal helical region extends to include residues 7-19, while the other helical region is slightly shortened. In the cyclo21-25 analogue, the C-terminal helical region is extended to include residues 19-28, while the N-terminal helical region is destabilized. The dicyclic analogue has the largest N-terminal helix, spanning residues 7-20, but its helical segment at residues 21-28 is not well ordered. All of the analogues exhibit substantial biological activity. The cyclic and dicyclic analogues show dramatically increased resistance to degradation during incubation with human plasma. The i-(i + 4) lactam, therefore, appears to be a synthetic means of stabilizing a local alpha-helical conformation, which may be of general use in the design of active, stable peptides.

Amino Acid Sequence↗
PubMed1992

Fast structure alignment for protein databank searching.

A fast method is described for searching and analyzing the protein structure databank. It uses secondary structure followed by residue matching to compare protein structures and is developed from a previous structural alignment method based on dynamic programming. Linear representations of secondary structures are derived and their features compared to identify equivalent elements in two proteins. The secondary structure alignment then constrains the residue alignment, which compares only residues within aligned secondary structures and with similar buried areas and torsional angles. The initial secondary structure alignment improves accuracy and provides a means of filtering out unrelated proteins before the slower residue alignment stage. It is possible to search or sort the protein structure databank very quickly using just secondary structure comparisons. A search through 720 structures with a probe protein of 10 secondary structures required 1.7 CPU hours on a Sun 4/280. Alternatively, combined secondary structure and residue alignments, with a cutoff on the secondary structure score to remove pairs of unrelated proteins from further analysis, took 10.1 CPU hours. The method was applied in searches on different classes of proteins and to cluster a subset of the databank into structurally related groups. Relationships were consistent with known families of protein structure.

Amino Acid Sequence↗
PubMed1992

Optimal checking procedures for monitoring laboratory analyses.

Many clinical, environmental, and epidemiologic studies rely heavily upon biochemical data, and the quality of these data is of paramount importance to the validity of study conclusions. Traditionally, far more attention has been given to the analysis of study data than has been given to monitoring the quality of the data. In this paper we draw an analogy between monitoring a laboratory system and an industrial production process and discuss the limitations of industrial quality control plans when applied in a laboratory setting. We derive methods for computing optimal checking schedules for laboratory analyses. These schedules formalize traditional laboratory practices of periodic checking and provide guidelines for the frequency and placement of checks within a finite batch of analyses. When laboratory system failure can be reasonably approximated by an exponential or geometric distribution, optimal checking schedules are relatively easy to compute. For more complex failure distributions, we present a dynamic programming approach. We describe an application to the measurement of selenium status in plasma samples using an electrothermal atomic absorption spectrophotometry procedure.

Algorithms↗