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

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↗

PubMed1976

Frequency of insertion-deletion, transversion, and transition in the evolution of 5S ribosomal RNA.

The problem of choosing an alignment of two or more nucleotide sequences is particularly difficult for nucleic acids, such as 5S ribosomal RNA, which do not code for protein and for which secondary structure is unknown. Given a set of 'costs' for the various types of replacement mutations and for base insertion or deletion, we present a dynamic programming algorithm which finds the optimal (least costly) alignment for a set of N sequences simultaneously, where each sequence is associated with one of the N tips of a given evolutionary tree. Concurrently, protosequences are constructed corresponding to the ancestral nodes of the tree. A version of this algorithm, modified to be computationally feasible, is implemented to align the sequences of 5S RNA from nine organisms. Complete sets of alignments and protosequence reconstructions are done for a large number of different configurations of mutation costs. Examination of the family of curbes of total replacements inferred versus the ratio of transitions/transversions inferred, each curve corresponding to a given number of insertions-deletions inferred, provides a method for estimating relative costs and relative frequencies for these different types of mutations.

Base Sequence↗

PubMed1991

A fast unbiased comparison of protein structures by means of the Needleman-Wunsch algorithm.

A fast dynamic programming algorithm for the spatial superposition of protein structure without prior knowledge of an initial alignment has been developed. The program was applied to serine proteases, hemoglobins, cytochromes C, small copper-binding proteins, and lysozymes. In most cases the existing structural homology could be detected in a completely unbiased way. The results of the method presented are in general agreement with other studies. Applying our method, the different alignment results obtained by other authors for serine proteases and cytochromes C can be classified in terms of different alignment parameters such as gap penalties or cut-off length. Limitations of the method are discussed.

Algorithms↗

PubMed1991

Knowledge-based system for the three-dimensional reconstruction of blood vessels from two angiographic projections.

A knowledge-based system for the three-dimensional reconstruction of blood vessels from wide-angle coronary and stereoscopic cerebral angiographic projections is developed. For the reconstruction of the coronary vessels, the left coronary artery (LCA) is automatically labelled on standard RAO and LAO projections, using anatomical models of the LCA. The labelling system succeeds in giving the most important coronary arteries a correct anatomical label. These labelling results enable us to find corresponding segments in both images. In the case of the reconstruction of the cerebral vessels however, such an anatomical model is clearly unavailable. To find corresponding segments, small-angle projections must be relied on, resulting in very similar images. Owing to the small angular separation between both projections, the three-dimensional reconstruction will be less accurate. Once the corresponding segments in both projections are obtained, the three-dimensional artery trajectory is reconstructed with dynamic programming techniques. The three-dimensional reconstructed coronary vessels are also used for an automatic quantification of stenotic lesions.

Blood Vessels↗

PubMed1992

Segmentation, modelling and reconstruction of arterial bifurcations in digital angiography.

The paper presents a method to model an arterial bifurcation from a pair of X-ray angiographic images. It is the initial step of a reconstruction process aiming at detecting and quantifying abnormal sites located on bifurcations. The method proposed consists of two steps. First, each image is independently segmented to extract the vessels in the images. The algorithm uses dynamic programming first to find the bifurcation centrelines from the original images, and secondly to extract vessel edges from the morphological gradient images, under a constraint of parallelism with the previously detected centrelines. Then, a three-dimensional bifurcation model is built by adapting cylinders around the three-dimensional bifurcation centrelines. These cylinders are obtained as a stack of binary orientable ellipses fitted to the projection densities in the corresponding cross-sections. Results obtained on simulated data, phantom and femoral bifurcations are displayed.

Angiography, Digital Subtraction↗

PubMed1989

The alignment of protein structures in three dimensions.

This article extends the use of dynamic programming algorithms in molecular sequence comparison to the alignment of the alpha-carbon (C alpha-) coordinates of two protein structures in three dimensions. The algorithm is described in detail and is applied to the comparison of alpha-lactalbumin with both hen egg white lysozyme and T4 lysozyme. In the first case, the structures are similar, while the second comparison is between two distantly related molecules. References are made to the usual sequence alignments. A variety of complementary methods are introduced to display the results.

Algorithms↗

PubMed1992

A local algorithm for DNA sequence alignment with inversions.

A dynamic programming algorithm to find all optimal alignments of DNA subsequences is described. The alignments use not only substitutions, insertions and deletions of nucleotides but also inversions (reversed complements) of substrings of the sequences. The inversion alignments themselves contain substitutions, insertions and deletions of nucleotides. We study the problem of alignment with non-intersecting inversions. To provide a computationally efficient algorithm we restrict candidate inversions to the K highest scoring inversions. An algorithm to find the J best non-intersecting alignments with inversions is also described. The new algorithm is applied to the regions of mitochondrial DNA of Drosophila yakuba and mouse coding for URF6 and cytochrome b and the inversion of the URF6 gene is found. The open problem of intersecting inversions is discussed.

Algorithms↗

PubMed1992

An O (N2 log N) restriction map comparison and search algorithm.

We present an O (R log P) time, O (M+P2) space algorithm for searching a restriction map with M sites for the best matches to a shorter map with P sites, where R, the number of matching site pairs, is bounded by MP. As first proposed by Waterman et al. (1984, Nucl. Acids Res. 12, 237-242) the objective function used to score matches is additive in the number of unaligned sites and the discrepancies in the distances between adjacent aligned sites. Our algorithm is basically a sparse dynamic programming computation in which "candidate lists" are used to model the future contribution of all previously computed entries to those yet to be computed. A simple modification to the algorithm computes the distance between two restriction maps with M and N sites, respectively, in O (MN (log M+log N)) time.

Algorithms↗

PubMed1992

Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons.

DNA and protein sequence comparisons are performed by a number of computational algorithms. Most of these algorithms search for the alignment of two sequences that optimizes some alignment score. It is an important problem to assess the statistical significance of a given score. In this paper we use newly developed methods for Poisson approximation to derive estimates of the statistical significance of k-word matches on a diagonal of a sequence comparison. We require at least q of the k letters of the words to match where 0 less than q less than or equal to k. The distribution of the number of matches on a diagonal is approximated as well as the distribution of the order statistics of the sizes of clumps of matches on the diagonal. These methods provide an easily computed approximation of the distribution of the longest exact matching word between sequences. The methods are validated using comparisons of vertebrate and E. coli protein sequences. In addition, we compare two HLA class II transplantation antigens by this method and contrast the results with a dynamic programming approach. Several open problems are outlined in the last section.

Algorithms↗

PubMed1989

Supercomputers and biological sequence comparison algorithms.

Comparison of biological (DNA or protein) sequences provides insight into molecular structure, function, and homology and is increasingly important as the available databases become larger and more numerous. One method of increasing the speed of the calculations is to perform them in parallel. We present the results of initial investigations using two dynamic programming algorithms on the Intel iPSC hypercube and the Connection Machine as well as an inexpensive, heuristically-based algorithm on the Encore Multimax.

Algorithms↗

PubMed1991

A parallel computing approach to genetic sequence comparison: the master-worker paradigm with interworker communication.

We have implemented a parallel version of a dynamic programming biological sequence comparison algorithm to study the potential applicability of using parallel computers for genetic sequence comparisons. Our parallel program is built using C-Linda, a machine-independent parallel programming language, and was tested on both a 10 CPU Sequent Symmetry and a 64 CPU Intel Hypercube. C-Linda implements a shared associative memory model, "tuple space," through which multiple processes can communicate and coordinate control. In our master-worker (MW) parallel implementation, a master process creates several worker processes, extracts a test sequence and multiple library sequences from a database and stores them in tuple space. Each worker reads the test sequence and then repeatedly extracts library strings from tuple space, performs pairwise sequence comparison using a local comparison algorithm to generate a similarity score, and returns the similarity scores to tuple space. The master collects the scores from tuple space and identifies the best match over all library sequences. We also implemented a method of global interworker communication to reduce the total search time by stopping those string comparisons that had no chance of improving on the current best match. Comparisons of the total run time, speedup, and efficiency were made for parallel and sequential versions of a basic MW implementation as well as versions with the global abort threshold.

Algorithms↗

PubMed1992

Basophil degranulation control.

We first present a global simulation model describing inhibition of human basophil degranulation by means of high dilutions. Then we study an optimal control problem associated to a non-linear compartmental model. This control is associated to an antigen concentration. For solving this control problem we used a dynamic programming method.

Basophil Degranulation Test↗

PubMed1989

Protein structure alignment.

A new method of comparing protein structures is described, based on distance plot analysis. It is relatively insensitive to insertions and deletions in sequence and is tolerant of the displacement of equivalent substructures between the two molecules being compared. When presented with the co-ordinate sets of two structures, the method will produce automatically an alignment of their sequences based on structural criteria. The method uses the dynamic programming optimization technique, which is widely used in the comparison of protein sequences and thus unifies the techniques of protein structure and sequence comparison. Typical structure comparison problems were examined and the results of the new method compared to the published results obtained using conventional methods. In most examples, the new method produced a result that was equivalent, and in some cases superior, to those reported in the literature.

Algorithms↗

PubMed1990

Flexible protein sequence patterns. A sensitive method to detect weak structural similarities.

The concept of a flexible protein sequence pattern is defined. In contrast to conventional pattern matching, template or sequence alignment methods, flexible patterns allow residue patterns typical of a complete protein fold to be developed in terms of residue positions (elements), separated by gaps of defined range. An efficient dynamic programming algorithm is presented to enable the best alignment(s) of a pattern with a sequence to be identified. The flexible pattern method is evaluated in detail by reference to the globin protein family, and by comparison to alignment techniques that exploit single sequence, multiple sequence and secondary structural information. A flexible pattern derived from seven globins aligned on structural criteria successfully discriminates all 345 globins from non-globins in the Protein Identification Resource database. Furthermore, a pattern that uses helical regions from just human alpha-haemoglobin identified 337 globins compared to 318 for the best non-pattern global alignment method. Patterns derived from successively fewer, yet more highly conserved positions in a structural alignment of seven globins show that as few as 38 residue positions (25 buried hydrophobic, 4 exposed and 9 others) may be used to uniquely identify the globin fold. The study suggests that flexible patterns gain discriminating power both by discarding regions known to vary within the protein family, and by defining gaps within specific ranges. Flexible patterns therefore provide a convenient and powerful bridge between regular expression pattern matching techniques and more conventional local and global sequence comparison algorithms.

Amino Acid Sequence↗

PubMed1991

Suboptimal sequence alignment in molecular biology. Alignment with error analysis.

A molecular sequence alignment algorithm based on dynamic programming has been extended to allow the computation of all pairs of residues that can be part of optimal and suboptimal sequence alignments. The uncertainties inherent in sequence alignment can be displayed using a new form of dot plot. The method allows the qualitative assessment of whether or not two sequences are related, and can reveal what parts of the alignment are better determined than others. It also permits the computation of representative optimal and suboptimal alignments. The relation between alignment reliability and alignment parameters is discussed. Other applications are to cyclical permutations of sequences and the detection of self-similarity. An application to multiple sequence alignment is noted.

Algorithms↗

PubMed1991

Relaxation matrix refinement of the solution structure of squash trypsin inhibitor.

The structure of the small squash trypsin inhibitor CMTI-I is refined by directly minimizing the difference between the observed two-dimensional nuclear Overhauser enhancement (NOE) intensities and those calculated by the full relaxation matrix approach. To achieve this, a term proportional to this difference was added to the potential energy function of the molecular dynamics program X-PLOR. Derivatives with respect to atomic co-ordinates are calculated analytically. Spin diffusion effects are thus accounted for fully during the refinement. Initial structures for the refinement were those determined recently by solution nuclear magnetic resonance using the isolated two-spin approximation to derive distance range estimates. The fits to the nuclear magnetic resonance data improve significantly with only small shifts in the refined structures during a few cycles of conjugate gradient minimization. However, larger changes (approximately 1 A) in the conformation occur during simulated annealing, which is accompanied by a further reduction of the difference between experimental and calculated two-dimensional NOE intensities. The refined structures are closer to the X-ray structure of the inhibitor complexed with trypsin than the initial structures. The root-mean-square difference for backbone atoms between the initial structures and the X-ray structure is 0.96 A, and that between the refined structures and the X-ray structure 0.61 A.

Magnetic Resonance Spectroscopy↗

PubMed1990

Reconstructing evolution of sequences subject to recombination using parsimony.

The parsimony principle states that a history of a set of sequences that minimizes the amount of evolution is a good approximation to the real evolutionary history of the sequences. This principle is applied to the reconstruction of the evolution of homologous sequences where recombinations or horizontal transfer can occur. First it is demonstrated that the appropriate structure to represent the evolution of sequences with recombinations is a family of trees each describing the evolution of a segment of the sequence. Two trees for neighboring segments will differ by exactly the transfer of a subtree within the whole tree. This leads to a metric between trees based on the smallest number of such operations needed to convert one tree into the other. An algorithm is presented that calculates this metric. This metric is used to formulate a dynamic programming algorithm that finds the most parsimonious history that fits a given set of sequences. The algorithm is potentially very practical, since many groups of sequences defy analysis by methods that ignore recombinations. These methods give ambiguous or contradictory results because the sequence history cannot be described by one phylogeny, but only a family of phylogenies that each describe the history of a segment of the sequences. The generalization of the algorithm to reconstruct gene conversions and the possibility for heuristic versions of the algorithm for larger data sets are discussed.

Algorithms↗