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 91 records · Page 5Linked to original sources
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↗
PubMed2026

Theseus: fast and optimal affine-gap sequence-to-graph alignment.

MOTIVATION: Sequence-to-graph alignment is a central problem in bioinformatics, with applications in multiple sequence alignment (MSA) and pangenome analysis, among others. However, current algorithms for optimal affine-gap alignment impose high memory and computational requirements, limiting their scalability to aligning long sequences to complex graphs. Practical solutions partially address this problem using heuristic strategies that ultimately trade off optimality for speed. RESULTS: This work presents Theseus, a novel, fast, and optimal affine-gap sequence-to-graph alignment algorithm. Theseus leverages similarities between genomic sequences to accelerate the alignment computation and reduces the overall memory requirements without compromising optimality. To that end, Theseus processes only a subset of the dynamic programming cells, using a sparse-data strategy that enables efficient sequence-to-graph alignment. Moreover, our algorithm supports optimal affine-gap alignment on arbitrary directed graphs, including those with cycles. We evaluate Theseus on two key problems: MSA and pangenome read mapping. For MSA, we compare it against SPOA, abPOA, and POASTA. Theseus is 1.6× to 17.6× faster than POASTA, and 7.3× faster, on average, than SPOA, both optimal aligners. Compared with abPOA, Theseus ensures optimality and scales to the largest problems. For pangenome read mapping, we benchmark Theseus against the alignment stage of the mapping tool vg map, along with the alignment kernels of SPOA, abPOA, and POASTA. Theseus outperforms the other methods, showing a 1.9× to 16.9× speedup on short reads. Moreover, Theseus is 1.5× to 36.3× faster than vg when aligning against synthetic cyclic graphs. AVAILABILITY AND IMPLEMENTATION: Theseus code and documentation are publicly available at https://github.com/albertjimenezbl/theseus-lib.

Algorithms↗
PubMed1988

Statistical analysis of DNA sequences.

Developments in the statistical analysis of DNA sequence data since 1984 are reviewed. Mathematical methods employing dynamic programming or incorporating Markov chain theory have been developed to search sequences for regions of similarity and to align sequences. When the biological forces of mutation and genetic drift are included in models, distances between aligned sequences allow the construction of evolutionary trees. Theory based on models may lead to estimates of variation of parameter estimates and so give a means of assessing the statistical significance of observed patterns and relationships. The complexity of DNA sequences, however, suggests that most statistical inferences will rest on random permutations of sequences.

Base Sequence↗
PubMed2025

Incorporating Epidemiological Data into the Genomic Analysis of Partially Sampled Infectious Disease Outbreaks.

Pathogen genomic data are increasingly being used to investigate transmission dynamics in infectious disease outbreaks. Combining genomic data with epidemiological data should substantially increase our understanding of outbreaks, but this is highly challenging when the outbreak under study is only partially sampled, so that both genomic and epidemiological data are missing for intermediate links in the transmission chains. Here, we present a new dynamic programming algorithm to perform this task efficiently. We implement this methodology into the well-established TransPhylo framework to reconstruct partially sampled outbreaks using a combination of genomic and epidemiological data. We use simulated datasets to show that including epidemiological data can improve the accuracy of the inferred transmission links compared with inference based on genomic data only. This also allows us to estimate parameters specific to the epidemiological data (such as transmission rates between particular groups), which would otherwise not be possible. We then apply these methods to two real-world examples. First, we use genomic data from an outbreak of tuberculosis in Argentina, for which data was also available on the HIV status of sampled individuals, in order to investigate the role of HIV coinfection in the spread of this tuberculosis outbreak. Second, we use genomic and geographical data from the 2003 epidemic of avian influenza H7N7 in the Netherlands to reconstruct its spatial epidemiology. In both cases, we show that incorporating epidemiological data into the genomic analysis allows us to investigate the role of epidemiological properties in the spread of infectious diseases.

Humans↗
PubMed1986

Algorithms for the search of amino acid patterns in nucleic acid sequences.

Some algorithms are described for the search of regions in a nucleic acid sequence that, when translated into amino acids, are homologous to a given amino acid pattern. All algorithms are modifications of the dynamic programming method for sequence comparison such that the translation of codons is taken into account. One of the algorithms has been implemented as a FORTRAN 77 program. The program operates on files that follow the format of the EMBL Nucleotide Sequence Data Library.

Amino Acid Sequence↗
PubMed1988

Multiple sequence alignment with hierarchical clustering.

An algorithm is presented for the multiple alignment of sequences, either proteins or nucleic acids, that is both accurate and easy to use on microcomputers. The approach is based on the conventional dynamic-programming method of pairwise alignment. Initially, a hierarchical clustering of the sequences is performed using the matrix of the pairwise alignment scores. The closest sequences are aligned creating groups of aligned sequences. Then close groups are aligned until all sequences are aligned in one group. The pairwise alignments included in the multiple alignment form a new matrix that is used to produce a hierarchical clustering. If it is different from the first one, iteration of the process can be performed. The method is illustrated by an example: a global alignment of 39 sequences of cytochrome c.

Algorithms↗
PubMed1988

An RNA secondary structure workbench.

A multiple approach to the study of RNA secondary structure is described which provides for the independent drawing of structures using base-pairing lists, for the generation of local structures in the form of hairpins, and for the generation of global structures by both Monte Carlo and dynamic programming methodologies. User-adjustable parameters provide for limiting the size of hairpin loops, bulges and inner loops, and constraints can be imposed relative to position-dependent base pairing.

Algorithms↗
PubMed1992

Crystallographic studies of a calcium binding lysozyme from equine milk at 2.5 A resolution.

The crystal structure of a calcium binding equine lysozyme has been determined at 2.5 A resolution by means of molecular replacement. The energy minimized equine lysozyme as the starting model, was refined with the molecular dynamics program, X-PLOR, and the R factor of the current model was found to be 24% without any water molecules. The conformation of the calcium binding loop is similar to that of alpha-lactalbumin. The profiles of backbone atomic displacements throughout the lysozyme and alpha-lactalbumin superfamilies are comparable as well as their homologous tertiary structures.

Amino Acid Sequence↗
PubMed1992

Search for the stable state of a short chain in a molecular field.

A general approach is developed to search for stable structures of short chain fragments (e.g. of loops or bound oligopeptides) in a given molecular field. This molecular field is produced by the remaining part of a globule or by any other surface with a defined spatial structure. The fragment must be short enough to have no pronounced long-range interactions within itself. The method is illustrated by calculation of the 3-D structures of two loops of bovine pancreatic trypsin inhibitor (BPTI). Computations are based on a lattice model of conformational space and on strict and fast algorithms of 1-D statistical mechanics and dynamic programming (which are very similar in essence). This makes a search of oligopeptide structures only several times (and not several orders of magnitude) longer than that of a dipeptide.

Algorithms↗
PubMed1992

A new approach to the design of a sequence with the highest affinity for a molecular surface.

We describe an algorithm to design the primary structures for peptides which must have the strongest binding to a given molecular surface. This problem cannot be solved by a direct combinatorial sorting, because of an enormous number of possible primary and spatial structures. The approach to solve this problem is to describe a state of each residue by two variables: (i) amino acid type and (ii) 3-D coordinate, and to minimize binding energy over all these variables simultaneously. For short chains which have no long-range interactions within themselves, this minimization can be done easily and efficiently by dynamic programming. We also discuss the problem of how to estimate specificity of binding and how to deduce a sequence with maximal specificity for a given surface. We show that this sequence can be deduced by the same algorithm after some modification of energetic parameters.

Algorithms↗
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↗
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×;. An optional mode permits a KuPID sample to be paired with both isoform discovery and transcript quantification.

Journal Article↗
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↗
PubMed1985

Numerical experiments with a new differentiation filter.

A dynamic programming filter which provides estimates of the first and second derivative of empirical displacement data is investigated numerically. This filter uses a weighted least squares criteria in estimating the derivatives. The filter equations are presented together with several numerical examples. These examples are taken from references that proposed other techniques.

Biomechanical Phenomena↗