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 73 records · Page 4Linked to original sources

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↗

PubMed1990

Use of homology domains in sequence similarity detection.

We have found the detection of homology domains using a nonlinear similarity score and the DD algorithm to be a useful approach for identifying similarity between sequences and evaluating potential homology. There are several reasons for the success of the method. (i) Homology domains are identified by a rigorous method that guarantees they will be locally optimal. (ii) The relative significance of different homology domains can be directly compared using the nonlinear similarity score. (iii) Different cost matrices can be used in the calculation of the similarity score. (iv) Relatively long sequences can be compared in a single pass as storage requirements are proportional to the shorter of the two sequences being compared. (v) The method has proved to be very sensitive in practice. (vi) The boundaries of authentic regions of homology are accurately identified. (vii) The information required to define a homology domain (its location, size, similarity score, etc.) can be stored in a compact data structure, facilitating the sharing of homology domain data among different software tools. (viii) The method can be applied to similarity searches of the nucleotide and protein sequence data banks. These properties make the identification of homology domains for studying sequence similarity a useful companion to other accepted methods, such as dynamic programming based analyses.

Animals↗

PubMed1990

Detecting pseudoknots and other local base-pairing structures in RNA sequences.

The current version of RNAFOLD now has the capability for conducting comparative studies relative to nonbifurcating hairpins contained in the global structures produced by the dynamic programming and Monte Carlo methods. It also has the capability of both finding and comparing hairpins and pseudoknots independently of global structures. The efficacy of these increased capabilities has been tested for select families of sequences, and the results thus far indicate favorable utility. Under consideration is a further extension designed to incorporate pseudoknots within global structures. Written in the C language, RNAFOLD and its companion program, GENALIGN, for doing multiple alignments in the comparison of pseudoknots and hairpins, is available for UNIX systems on standard 1/2-inch, 9-track tape or on SUN tape cartridges.

Base Sequence↗

PubMed1990

Hierarchical method to align large numbers of biological sequences.

The method presented here is intended as a compromise between finding a good overall alignment and the time taken to do so. Many multiple alignment algorithms spend an excessively large amount of effort trying to find the best global alignment. This time is often ill spent because the results of the standard dynamic programming alignment algorithm are dominated by the choice of gap penalty and the form of the score matrix, both of which have a poor theoretical foundation. Nonetheless, it is important that savings in time do not compromise the quality of the alignment. By using the consensus sequence approach, this danger is largely avoided as the conserved features of the sequences are quickly identified and preserved through further cycles. In the alignment of existing alignments, which is one of the more novel aspects of the method, each alignment was treated as an averaged consensus sequence with gaps making no contribution. This gives rise to the advantageous property that gaps will have a greater propensity to be inserted where there are already gaps and is equivalent to a local change in the gap penalty. This type of behavior represents a transition away from the homogeneous scoring schemes used in aligning two sequences toward a scoring scheme that depends on position in the sequence. The alignment of consensus sequences thus forms a bridge between simple pair alignment and the alignment of discrete patterns in which sequence features and allowed gap locations are exaggerated. To complete this transition the program described above has been integrated into the earlier pattern matching (template) program. Such templates can reliably locate sequence similarities that are too weak or scattered to be found by the more standard alignment methods and should therefore produce a further condensation of the sequence data bank. Only by continually extending our knowledge of the relationships between sequences to increasingly distant similarities can we hope to avoid being overwhelmed by the increasing amount of data.

Algorithms↗

PubMedDate not supplied

Recognition of regions in brain sections.

This paper addresses the problem of region identification in sequential brain sections and presents a recognition system that finds and tracks region boundaries in those sections. The characteristics of the areas of interest are unique in one sense because they are not stationary. Some regions are hardly discernible. In others, parts of the boundary are missing or so completely blurred that parts of the background may be considered as an extension of the region itself. Moreover, outliers are likely to exist in many cases. Due to the unique properties of brain regions, the emphasis is on robustification and efficiency. The region segmentation problem was expressed as a multi-hypothesis test seeking boundaries that maximize a performance criterion which is general in terms of blur and noise. Boundary candidates are restricted to an adaptive search area around a reference boundary which is usually the outcome of the algorithm from the previous section. The search for the maximum criterion uses a fast first order dynamic programing (DP) procedure, reducing the processing time. Outlier rejection techniques are integrated with the multi-hypothesis test to compensate for both outliers and noise. The result is the reference for the next section. Experimental results on boundary detection are presented. The algorithm is successful in tracing boundaries when the contrast is smaller than the noise power, and when parts of the outlines are missing.

Algorithms↗

PubMed1992

NMR analysis of helix I from the 5S RNA of Escherichia coli.

The structure of helix I of the 5S rRNA from Escherichia coli has been determined using a nucleolytic digest fragment of the intact molecule. The fragment analyzed, which corresponds to bases (-1)-11 and 108-120 of intact 5S rRNA, contains a G-U pair and has unpaired bases at its termini. Its proton resonances were assigned by two-dimensional NMR methods, and both NOE distance and coupling constant information have been used to calculate structural models for it using the full relaxation matrix algorithm of the molecular dynamics program XPLOR. Helix I has A-type helical geometry, as expected. Its most striking departure from regular helical geometry occurs at its G-U, which stacks on the base pair to the 5' side of its G but not on the base pair to its 3' side. This stacking pattern maximizes interstrand guanine-guanine interactions and explains why the G-U in question fails to give imino proton NOE's to the base pair to 5' side of its G. These results are consistent with the crystal structures that have been obtained for wobble base pairs in tRNAPhe [Mizuno, H., & Sundaralingam, M. (1978) Nucleic Acids Res. 5, 4451-4461] and A-form DNA [Rabbinovich, D., Haran, T., Eisenstein, M., & Shakked, Z. (1988) J. Mol. Biol. 200, 151-161]. The conformations of the terminal residues of helix I, which corresponds to bases (-1)-11 and 108-120 of native 5S RNA, are less well-determined, and their sugar puckers are intermediate between C2' and C3'-endo, on average.

Base Composition↗

PubMed1987

Profile analysis: detection of distantly related proteins.

Profile analysis is a method for detecting distantly related proteins by sequence comparison. The basis for comparison is not only the customary Dayhoff mutational-distance matrix but also the results of structural studies and information implicit in the alignments of the sequences of families of similar proteins. This information is expressed in a position-specific scoring table (profile), which is created from a group of sequences previously aligned by structural or sequence similarity. The similarity of any other sequence (target) to the group of aligned sequences (probe) can be tested by comparing the target to the profile using dynamic programming algorithms. The profile method differs in two major respects from methods of sequence comparison in common use: (i) Any number of known sequences can be used to construct the profile, allowing more information to be used in the testing of the target than is possible with pairwise alignment methods. (ii) The profile includes the penalties for insertion or deletion at each position, which allow one to include the probe secondary structure in the testing scheme. Tests with globin and immunoglobulin sequences show that profile analysis can distinguish all members of these families from all other sequences in a database containing 3800 protein sequences.

Amino Acid Sequence↗

PubMed1990

Automatic generation of primary sequence patterns from sets of related protein sequences.

We have developed a computer algorithm that can extract the pattern of conserved primary sequence elements common to all members of a homologous protein family. The method involves clustering the pairwise similarity scores among a set of related sequences to generate a binary dendrogram (tree). The tree is then reduced in a stepwise manner by progressively replacing the node connecting the two most similar termini by one common pattern until only a single common "root" pattern remains. A pattern is generated at a node by (i) performing a local optimal alignment on the sequence/pattern pair connected by the node with the use of an extended dynamic programming algorithm and then (ii) constructing a single common pattern from this alignment with a nested hierarchy of amino acid classes to identify the minimal inclusive amino acid class covering each paired set of elements in the alignment. Gaps within an alignment are created and/or extended using a "pay once" gap penalty rule, and gapped positions are converted into gap characters that function as 0 or 1 amino acid of any type during subsequent alignment. This method has been used to generate a library of covering patterns for homologous families in the National Biomedical Research Foundation/Protein Identification Resource protein sequence data base. We show that a covering pattern can be more diagnostic for sequence family membership than any of the individual sequences used to construct the pattern.

Amino Acid Sequence↗

PubMed1992

Parametric sequence comparisons.

Current algorithms can find optimal alignments of two nucleic acid or protein sequences, often by using dynamic programming. While the choice of algorithm penalty parameters greatly influences the quality of the resulting alignments, this choice has been done in an ad hoc manner. In this work, we present an algorithm to efficiently find the optimal alignments for all choices of the penalty parameters. It is then possible to systematically explore these alignments for those with the most biological or statistical interest. Several examples illustrate the method.

Algorithms↗

PubMed1988

Profile scanning for three-dimensional structural patterns in protein sequences.

Profile analysis measures the similarity between a target sequence and a group of aligned sequences (the probe). The probe sequences are used to produce a position-specific scoring table (the profile) that can be aligned with any sequence (the target) using standard dynamic programming methods. We are developing a library of profiles, each describing a different structural motif. This allows any target sequence to be rapidly scanned for the presence of structural motifs. Levels of significance for the comparison of target sequences with the profile are determined in advance, permitting an objective decision to be made as to whether a protein is likely to possess a structural motif.

Amino Acid Sequence↗

PubMed1989

RNA secondary structures: comparison and determination of frequently recurring substructures by consensus.

A method for assessing the preserved stem-loops of RNA secondary structures is presented. Frequently recurring helical stems in a set of secondary structures resulting from the simulated folding process of a given RNA are assessed and consensus structural motifs can then be selected to construct a secondary structure of the RNA. Alternatively, it can be applied to a series of 'optimal' and 'suboptimal' secondary structures computed using the dynamic program developed by Williams and Tinoco. To demonstrate the power and the usefulness of the program we give examples of this procedure.

Algorithms↗

PubMed1991

Scanning protein sequence databanks using a distributed processing workstation network.

The programme pscan has been developed to distribute protein databank scans over a network of computers that share a common file system. pscan may be used in conjunction with most conventional sequence comparison programmes with few modifications. In test runs using the Smith-Waterman dynamic programming algorithm, the time required to scan a 6858 sequence databank using a query sequence 740 residues long was reduced from approximately 50 min for a single processor, to approximately 11 minutes for five processors. Accordingly, pscan provides a low-cost, portable alternative to dedicated parallel processing computers.

Algorithms↗

PubMed1992

Statistical distance between texts and filtration methods in sequence comparison.

Upon searching local similarities in long sequences, the necessity of a 'rapid' similarity search becomes acute. Quadratic complexity of dynamic programming algorithms forces the employment of filtration methods that allow elimination of the sequences with a low similarity level. The paper is devoted to the theoretical substantiations of the filtration method based on the statistical distance between texts. The notion of the filtration efficiency is introduced and the efficiency of several filters is estimated. It is shown that the efficiency of the statistical l-tuple filtration upon DNA database search is associated with a potential extension of the original four-letter alphabet and grows exponentially with increasing l. The formula that allows one to estimate the filtration parameters is presented.

Amino Acid Sequence↗

PubMed1992

Parallelization of a local similarity algorithm.

The local similarity problem is to determine the similar regions within two given sequences. We recently developed a dynamic programming algorithm for the local similarity problem that requires only space proportional to the sum of the two sequence lengths, whereas earlier methods use space proportional to the product of the lengths. In this paper, we describe how to parallelize the new algorithm and present results of experimental studies on an Intel hypercube. The parallel method provides rapid, high-resolution alignments for users of our software toolkit for pairwise sequence comparison, as illustrated here by a comparison of the chloroplast genomes of tobacco and liverwort.

Algorithms↗

PubMed1992

Base-pair probability profiles of RNA secondary structures.

Dynamic programming algorithms are able to predict optimal and suboptimal secondary structures of RNA. These suboptimal or alternative secondary structures are important for the biological function of RNA. The distribution of secondary structures present in solution is governed by the thermodynamic equilibrium between the different structures. An algorithm is presented which approximates the total partition function by a Boltzmann-weighted summation of optimal and suboptimal secondary structures at several temperatures. A clear representation of the equilibrium distribution of secondary structures is derived from a two-dimensional bonding matrix with base-pairing probability as the third dimension. The temperature dependence of the equilibrium distribution gives the denaturation behavior of the nucleic acid, which may be compared to experimental optical denaturation curves after correction for the hypochromicities of the different base-pairs. Similarly, temperature-induced mobility changes detected in temperature-gradient gel electrophoresis of nucleic acids may be interpreted on the basis of the temperature dependence of the equilibrium distribution. Results are illustrated for natural circular and synthetic linear potato spindle tuber viroid RNA respectively, and are compared to experimental data.

Algorithms↗