Protein threading by recursive dynamic programming.

We present the recursive dynamic programming (RDP) method for the threading approach to three-dimensional protein structure prediction. RDP is based on the divide-and-conquer paradigm and maps the protein sequence whose backbone structure is to be found (the protein target) onto the known backbone structure of a model protein (the protein template) in a stepwise fashion, a technique that is similar to computing local alignments but utilising different cost functions. We begin by mapping parts of the target onto the template that show statistically significant similarity with the template sequence. After mapping, the template structure is modified in order to account for the mapped target residues. Then significant similarities between the yet unmapped parts of the target and the modified template are searched, and the resulting segments of the target are mapped onto the template. This recursive process of identifying segments in the target to be mapped onto the template and modifying the template is continued until no significant similarities between the remaining parts of target and template are found. Those parts which are left unmapped by the procedure are interpreted as gaps.The RDP method is robust in the sense that different local alignment methods can be used, several alternatives of mapping parts of the target onto the template can be handled and compared in the process, and the cost functions can be dynamically adapted to biological needs.Our computer experiments show that the RDP procedure is efficient and effective. We can thread a typical protein sequence against a database of 887 template domains in about 12 hours even on a low-cost workstation (SUN Ultra 5). In statistical evaluations on databases of known protein structures, RDP significantly outperforms competing methods. RDP has been especially valuable in providing accurate alignments for modeling active sites of proteins.RDP is part of the ToPLign system (GMD Toolbox for protein alignment) and can be accessed via the WWW independently or in concert with other ToPLign tools at http://cartan.gmd.de/ToPLign.html.     

Optimization of fed-batch fermentors by iterative dynamic programming

By using penalty functions to handle state constraints, iterative dynamic programming can be used in a straightforward manner for the optimization of fedbatch fermentors. No computational difficulties were encountered and better results are obtained than previously reported in the literature for a fed-batch fermentor for biosynthesis of penicillin. (c) 1993 Johy Wiley & Sons, Inc.     

Optimization of CSTRs in series by dynamic programming

This article concerns the development of a simple yet effective procedure for optimizing the design of a reactor system employing CSTRs in series. The basic approach used in this work was to translate the problem of reactor design to a mathematical programming model. The resulting model was then solved by dynamic programming. The procedure was tested on an IBM 3033 computer and an IBM PC-compatible machine, the CORONA PC-II microcomputer. The results of this study indicate that the optimization procedure developed is very effective.     

Determining minimum energy conformations of polypeptides by dynamic programming

A combinatorial optimization approach is used for solving the multiple-minima problem when determining the low-energy conformations of short polypeptides. Each residue is represented by a finite number of discrete states corresponding to single residue local minima of the energy function. These precomputed values constitute a search table and define the conformational space for discrete minimization by a generalized dynamic programming algorithm that significantly limits the number of intermediate conformations to be generated during the search. Since dynamic programming involves stagewise decisions, it results in buildup-type procedures implemented in two different forms. The first procedure predicts a number of conformations by a completely discrete search and these are subsequently refined by local minimization. The second involves limited continuous local minimization within the combinatorial algorithm, generally restricted to two dihedral angles in a buildup step. Both procedures are tested on 17 short peptides previously studied by other global minimization methods but involving the same potential energy function. The discrete method is extremely fast, but proves to be successful only in 14 of the 17 test problems. The version with limited local minimization finds, however, conformations in all the 17 examples that are close to the ones previously presented in the literature or have lower energies. In addition, results are almost independent of the cutoff energy, the most important parameter governing the search. Although the limited local minimization increases the number of energy evaluations, the method still offers substantial advantages in speed.     

Mapping biomedical terminologies using natural language processing tools and UMLS: Mapping the Orphanet thesaurus to the MeSH

BackgroundOrphanet aims to provide rare disease information to healthcare professionals, patients, and their relatives.ObjectiveThe objective of this work is to evaluate two methodologies (Unified Medical Languages Systems [UMLS] and manual Orphanet-ICD-10 link-based mapping & string-based matching) used to map Orphanet thesaurus to the MeSH thesaurus.ResultsOn a corpus of 375 mappings, the string-based matching provides significantly better results than the UMLS and manual Orphanet-ICD-10 link-based mapping.ConclusionString-based matching could be applied to any biomedical terminology in French not yet included into UMLS.     

Long term shear effects on a hybridoma cell line by dynamic perfusion devices

The long term shear effects on a hybridoma cell line were studied by the simulation of a hollow fiber perfusion system. Various mechanical/environmental stress conditions were applied and steady state concentrations of live, dead and lysed cells were measured or calculated in a continuous culture. From mathematical modeling, it is shown that inclusion of a lysed cell index (LCI) renders a better fit to the material balance equation at steady state. The specific cell death rate increased with increasing shear force as expected only when the LCI was included. Without the inclusion of the LCI, the calculated specific cell growth rates are about 25–60% of the value when included. The results reported may lend some insight to design improvements since most perfusion devices add shear stresses to the cells in the reactor.List of Symbols b ml/hr continuous culture flow rate - D hr^–1 dilution rate (b/V) - m g glucose/10⁹ cells/hr specific maintenance coefficient - S ₀ g/l feed substrate concentration - S g/l reactor substrate concentration - t hr time - V ml reactor volume - X ⁺ cells/ml live cell concentration - X ^– cells/ml dead cell concentration - X ⁰ cells/ml lysed cell concentration - Y _x/s 10⁹ cells/g glucose cell/substrate yield coefficient - hr^–1 specific growth rate - hr^–1 specific death rate - hr^–1 specific lysis rate - hr^–1 specific lysis rate for simultaneous death and lysis     

Information processing in neural networks by means of controlled dynamic regimes

This paper is concerned with the modeling of neural systems regarded as information processing entities. I investigate the various dynamic regimes that are accessible in neural networks considered as nonlinear adaptive dynamic systems. The possibilities of obtaining steady, oscillatory or chaotic regimes are illustrated with different neural network models. Some aspects of the dependence of the dynamic regimes upon the synaptic couplings are examined. I emphasize the role that the various regimes may play to support information processing abilities. I present an example where controlled transient evolutions in a neural network, are used to model the regulation of motor activities by the cerebellar cortex.     

HTJoinSolver: Human immunoglobulin VDJ partitioning using approximate dynamic programming constrained by conserved motifs

Background

Partitioning the human immunoglobulin variable region into variable (V), diversity (D), and joining (J) segments is a common sequence analysis step. We introduce a novel approximate dynamic programming method that uses conserved immunoglobulin gene motifs to improve performance of aligning V-segments of rearranged immunoglobulin (Ig) genes. Our new algorithm enhances the former JOINSOLVER algorithm by processing sequences with insertions and/or deletions (indels) and improves the efficiency for large datasets provided by high throughput sequencing.

Results

In our simulations, which include rearrangements with indels, the V-matching success rate improved from 61% for partial alignments of sequences with indels in the original algorithm to over 99% in the approximate algorithm. An improvement in the alignment of human VDJ rearrangements over the initial JOINSOLVER algorithm was also seen when compared to the Stanford.S22 human Ig dataset with an online VDJ partitioning software evaluation tool.

Conclusions

HTJoinSolver can rapidly identify V- and J-segments with indels to high accuracy for mutated sequences when the mutation probability is around 30% and 20% respectively. The D-segment is much harder to fit even at 20% mutation probability. For all segments, the probability of correctly matching V, D, and J increases with our alignment score.     

MASCOT: multiple alignment system for protein sequences based on three-way dynamic programming

A multiple alignment methodology that can produce high-qualityalignment is extremely important for predicting the structureof unknown proteins. Nearly all the methodologies developedso far have employed two-way alignment only. Although thesemethods are fast, the alignments they produce lose reliabilityas the similarity of sequences reduces. We developed the MASCOTmultiple alignment system. MASCOT can sustain the reliabilityof alignment even when the similarity of sequences is low. MASCOTachieves high-quality alignment by employing three-way alignmentin addition to two-way alignment. The resultant alignments arerefined by simulated annealing to higher quality. We also usea cluster analysis of sequences to produce highly reliable alignments.     

Factors influencing route choice by avian migrants: a dynamic programming model of Pacific brant migration

We used stochastic dynamic programming to investigate a spectacular migration strategy in the black brant Branta bernicla nigricans, a species of goose. Black brant migration is well suited for theoretical analysis since there are a number of existing strategies that easily can be compared. In early autumn, almost the entire population of the black brant gathers at Izembek Lagoon on the Alaska Peninsula to stage and refuel before the southward migration. There are at least three distinct strategies, with most geese making a spectacular direct migration more than 5000km across the Gulf of Alaska to their wintering grounds in southern Baja California or mainland Mexico. This is a potentially dangerous strategy since foraging is not possible during the overseas passage. Some individuals instead use shorter flights to make a detour along the coast, a longer route that all individuals use for northwards migration in spring. Since flight costs accelerate with increasing body mass, migration by short flights is energetically cheaper than long-distance flights. A small but increasing part of the population has recently begun to winter at Izembek. We investigated this migration under two different suppositions using a dynamic state variable model. First, if the geese are free to make a strategic choice, under what assumptions should they prefer direct migration and under what assumptions should they prefer detour migration/winter residency? Second, provided that the dominating direct migration strategy is optimal, what conditions will force the geese to go for detour migration/winter residency? In the second case the geese may try to follow an optimal direct migration strategy, but stochastic events may force them to choose a suboptimal policy. We also simulated possible effects of global warming. The model suggests that the fuel level at arrival in Izembek and fuel gain rates are key factors and that tail winds must have been reliable in the past, otherwise direct migration could not have evolved. It also suggests that a change to milder winters may promote an unexpectedly abrupt change from long-distance to short-distance migration or winter residency. Finally, it produced a number of predictions that might be testable in the field.     

Derivative-free neural network for optimizing the scoring functions associated with dynamic programming of pairwise-profile alignment

Background

A profile-comparison method with position-specific scoring matrix (PSSM) is among the most accurate alignment methods. Currently, cosine similarity and correlation coefficients are used as scoring functions of dynamic programming to calculate similarity between PSSMs. However, it is unclear whether these functions are optimal for profile alignment methods. By definition, these functions cannot capture nonlinear relationships between profiles. Therefore, we attempted to discover a novel scoring function, which was more suitable for the profile-comparison method than existing functions, using neural networks.

Results

Although neural networks required derivative-of-cost functions, the problem being addressed in this study lacked them. Therefore, we implemented a novel derivative-free neural network by combining a conventional neural network with an evolutionary strategy optimization method used as a solver. Using this novel neural network system, we optimized the scoring function to align remote sequence pairs. Our results showed that the pairwise-profile aligner using the novel scoring function significantly improved both alignment sensitivity and precision relative to aligners using existing functions.

Conclusions

We developed and implemented a novel derivative-free neural network and aligner (Nepal) for optimizing sequence alignments. Nepal improved alignment quality by adapting to remote sequence alignments and increasing the expressiveness of similarity scores. Additionally, this novel scoring function can be realized using a simple matrix operation and easily incorporated into other aligners. Moreover our scoring function could potentially improve the performance of homology detection and/or multiple-sequence alignment of remote homologous sequences. The goal of the study was to provide a novel scoring function for profile alignment method and develop a novel learning system capable of addressing derivative-free problems. Our system is capable of optimizing the performance of other sophisticated methods and solving problems without derivative-of-cost functions, which do not always exist in practical problems. Our results demonstrated the usefulness of this optimization method for derivative-free problems.

     

Monitoring for dynamic biological processing by intramolecular bioluminescence resonance energy transfer system using secreted luciferase

Proteolytic processing plays crucial roles in physiological and pathophysiological cellular functions such as peptide generation, cell cycle, and apoptosis. We developed a novel biophysical bioluminescence resonance energy transfer (BRET) system between a secreted Vargula luciferase (Vluc) and an enhanced yellow fluorescent protein (EYFP) for visualization of cell biological processes. The bioluminescence spectrum of the fusion protein (Vluc-EYFP) is bimodal (lambdamax = 460 nm (Vluc) and 525nm (EYFP)), indicating that the excited-state energy of Vluc transfers to EYFP (in short, BRET). The BRET signal can be measured in the culture medium and pursue quantitative production of two neuropeptides, nocistatin (NST) and nociceptin/orphanin FQ (N/OFQ) in living cells. NST and N/OFQ are located in tandem on the same precursor, but NST exhibits antagonistic action against N/OFQ-induced central functions. Insertion of a portion of the NST-N/OFQ precursor (Glu-Gln-Lys-Gln-Leu-Gln-Lys-Arg-Phe-Gly-Gly-Phe-Tyr-Gly) in Vluc-EYFP makes the fusion protein cleavable at Lys-Arg in NG108-15 cells, and proprotein convertase 1 enhances this digestion. The change in BRET signals quantifies the processing of the fusion protein. Our novel intramolecular BRET system using a secreted luciferase is useful for investigating peptide processing in living cells.     

Automatic detection of the carotid artery boundary on cross-sectional MR image sequences using a circle model guided dynamic programming

Background  

Systematic aerobe training has positive effects on the compliance of dedicated arterial walls. The adaptations of the arterial structure and function are associated with the blood flow-induced changes of the wall shear stress which induced vascular remodelling via nitric oxide delivered from the endothelial cell. In order to assess functional changes of the common carotid artery over time in these processes, a precise measurement technique is necessary. Before this study, a reliable, precise, and quick method to perform this work is not present.     

Antigen processing by the proteasome

The proteasome is an essential part of our immune surveillance mechanisms: by generating peptides from intracellular antigens it provides peptides that are then 'presented' to T cells. But proteasomes--the waste-disposal units of the cell--typically do not generate peptides for antigen presentation with high efficiency. How, then, does the proteasome adapt to serve the immune system well?     

Prediction of protein secondary structure based on residue pair types and conformational states using dynamic programming algorithm

We have used a statistical approach for protein secondary structure prediction based on information theory and simultaneously taking into consideration pairwise residue types and conformational states. Since the prediction of residue secondary structure by one residue window sliding make ambiguity in state prediction, we used a dynamic programming algorithm to find the path with maximum score. A score system for residue pairs in particular conformations is derived for adjacent neighbors up to ten residue apart in sequence. The three state overall per-residue accuracy, Q3, of this method in a jackknife test with dataset created from PDBSELECT is more than 70%.