A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.

Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components; then, in the second stage, certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an O(nalpha(n)) algorithm, based on a Union-Find structure, to find its connected components, where alpha is the inverse Ackerman function. Since for all practical purposes alpha(n) is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.     

Automated scaffold selection for enzyme design

A major goal of computational protein design is the construction of novel functions on existing protein scaffolds. There the first question is which scaffold is suitable for a specific reaction. Given a set of catalytic residues and their spatial arrangement, one wants to identify a protein scaffold that can host this active site. Here, we present an algorithm called ScaffoldSelection that is able to rapidly search large sets of protein structures for potential attachment sites of an enzymatic motif. The method consists of two steps; it first identifies pairs of backbone positions in pocket‐like regions. Then, it combines these to complete attachment sites using a graph theoretical approach. Identified matches are assessed for their ability to accommodate the substrate or transition state. A representative set of structures from the Protein Data Bank (～3500) was searched for backbone geometries that support the catalytic residues for 12 chemical reactions. Recapitulation of native active site geometries is used as a benchmark for the performance of the program. The native motif is identified in all 12 test cases, ranking it in the top percentile in 5 out of 12. The algorithm is fast and efficient, although dependent on the complexity of the motif. Comparisons to other methods show that ScaffoldSelection performs equally well in terms of accuracy and far better in terms of speed. Thus, ScaffoldSelection will aid future computational protein design experiments by preselecting protein scaffolds that are suitable for a specific reaction type and the introduction of a predefined amino acid motif. Proteins 2009. © 2009 Wiley‐Liss, Inc.     

Efficient formulations for exact stochastic simulation of chemical systems

One can generate trajectories to simulate a system of chemical reactions using either Gillespie's direct method or Gibson and Bruck's next reaction method. Because one usually needs many trajectories to understand the dynamics of a system, performance is important. In this paper, we present new formulations of these methods that improve the computational complexity of the algorithms. We present optimized implementations, available from http://cain.sourceforge.net/, that offer better performance than previous work. There is no single method that is best for all problems. Simple formulations often work best for systems with a small number of reactions, while some sophisticated methods offer the best performance for large problems and scale well asymptotically. We investigate the performance of each formulation on simple biological systems using a wide range of problem sizes. We also consider the numerical accuracy of the direct and the next reaction method. We have found that special precautions must be taken in order to ensure that randomness is not discarded during the course of a simulation.     

A graph layout algorithm for drawing metabolic pathways

MOTIVATION: A large amount of data on metabolic pathways is available in databases. The ability to visualise the complex data dynamically would be useful for building more powerful research tools to access the databases. Metabolic pathways are typically modelled as graphs in which nodes represent chemical compounds, and edges represent chemical reactions between compounds. Thus, the problem of visualising pathways can be formulated as a graph layout problem. Currently available visual interfaces to biochemical databases either use static images or cannot cope well with more complex, non-standard pathways. RESULTS: This paper presents a new algorithm for drawing pathways which uses a combination of circular, hierarchic and force-directed graph layout algorithms to compute positions of the graph elements representing main compounds and reactions. The algorithm is particularly designed for cyclic or partially cyclic pathways or for combinations of complex pathways. It has been tested on five sample pathways with promising results.     

Influence of prior knowledge in constraint-based learning of gene regulatory networks

Constraint-based structure learning algorithms generally perform well on sparse graphs. Although sparsity is not uncommon, there are some domains where the underlying graph can have some dense regions; one of these domains is gene regulatory networks, which is the main motivation to undertake the study described in this paper. We propose a new constraint-based algorithm that can both increase the quality of output and decrease the computational requirements for learning the structure of gene regulatory networks. The algorithm is based on and extends the PC algorithm. Two different types of information are derived from the prior knowledge; one is the probability of existence of edges, and the other is the nodes that seem to be dependent on a large number of nodes compared to other nodes in the graph. Also a new method based on Gene Ontology for gene regulatory network validation is proposed. We demonstrate the applicability and effectiveness of the proposed algorithms on both synthetic and real data sets.     

Reaction Factoring and Bipartite Update Graphs Accelerate the Gillespie Algorithm for Large-Scale Biochemical Systems

ODE simulations of chemical systems perform poorly when some of the species have extremely low concentrations. Stochastic simulation methods, which can handle this case, have been impractical for large systems due to computational complexity. We observe, however, that when modeling complex biological systems: (1) a small number of reactions tend to occur a disproportionately large percentage of the time, and (2) a small number of species tend to participate in a disproportionately large percentage of reactions. We exploit these properties in LOLCAT Method, a new implementation of the Gillespie Algorithm. First, factoring reaction propensities allows many propensities dependent on a single species to be updated in a single operation. Second, representing dependencies between reactions with a bipartite graph of reactions and species requires only storage for reactions, rather than the required for a graph that includes only reactions. Together, these improvements allow our implementation of LOLCAT Method to execute orders of magnitude faster than currently existing Gillespie Algorithm variants when simulating several yeast MAPK cascade models.     

New algorithms and an in silico benchmark for computational enzyme design

The creation of novel enzymes capable of catalyzing any desired chemical reaction is a grand challenge for computational protein design. Here we describe two new algorithms for enzyme design that employ hashing techniques to allow searching through large numbers of protein scaffolds for optimal catalytic site placement. We also describe an in silico benchmark, based on the recapitulation of the active sites of native enzymes, that allows rapid evaluation and testing of enzyme design methodologies. In the benchmark test, which consists of designing sites for each of 10 different chemical reactions in backbone scaffolds derived from 10 enzymes catalyzing the reactions, the new methods succeed in identifying the native site in the native scaffold and ranking it within the top five designs for six of the 10 reactions. The new methods can be directly applied to the design of new enzymes, and the benchmark provides a powerful in silico test for guiding improvements in computational enzyme design.     

Enzyme Kinetics for Complex System Enables Accurate Determination of Specificity Constants of Numerous Substrates in a Mixture by Proteomics Platform

Many important experiments in proteomics including protein digestion, enzyme substrate screening, enzymatic labeling, etc., involve the enzymatic reactions in a complex system where numerous substrates coexists with an enzyme. However, the enzyme kinetics in such a system remains unexplored and poorly understood. Herein, we derived and validated the kinetics equations for the enzymatic reactions in complex system. We developed an iteration approach to depict the enzymatic reactions in complex system. It was validated by 630 time-course points from 24 enzymatic reaction experiments and was demonstrated to be a powerful tool to simulate the reactions in the complex system. By applying this approach, we found that the ratio of substrate depletion is independent of other coexisted substrates under specific condition. This observation was then validated by experiments. Based on this striking observation, a simplified model was developed to determine the catalytic efficiencies of numerous competing substrates presented in the complex enzyme reaction system. When coupled with high-throughput quantitative proteomics technique, this simplified model enabled the accurate determination of catalytic efficiencies for 2369 peptide substrates of a protease by using only one enzymatic reaction experiment. Thus, this study provided, in the first time, a validated model for the large scale determination of specificity constants which could enable the enzyme substrate screening approach turned from a qualitative method of identifying substrates to a quantitative method of identifying and prioritizing substrates. Data are available via ProteomeXchange with identifier PXD004665.     

A colorimetric 96-well microtiter plate assay for the determination of enzymatically formed citrulline

l-Citrulline constitutes a product of a number of enzymatic reactions. In the past a number of colorimetric methods for the determination of l-citrulline, upon its chemical modification with diacetyl monoxime at 95 degrees C, have been reported. However, all these methods are time- and material-consuming. In this work, using the same chemical reaction, a new method for the use in 96-well polystyrene microtiter plates was developed. The method is fast and requires substantially less material as the enzymatic reaction is performed in a volume of 60 microl. The applicability of this enzymatic assay was established using l-N(omega), N(omega)-dimethylarginine dimethylaminohydrolase, which generates l-citrulline from side-chain methylated derivatives of l-arginine. The detection limit for l-citrulline is about 0.2 nmol. In addition, our studies show that most commonly used biochemical buffers and buffer additives do not affect the assay. This method may prove useful in the studies of other l-citrulline producing enzymes including nitric oxide synthase.     

Metabolic network alignment in large scale by network compression

Metabolic network alignment is a system scale comparative analysis that discovers important similarities and differences across different metabolisms and organisms. Although the problem of aligning metabolic networks has been considered in the past, the computational complexity of the existing solutions has so far limited their use to moderately sized networks. In this paper, we address the problem of aligning two metabolic networks, particularly when both of them are too large to be dealt with using existing methods. We develop a generic framework that can significantly improve the scale of the networks that can be aligned in practical time. Our framework has three major phases, namely the compression phase, the alignment phase and the refinement phase. For the first phase, we develop an algorithm which transforms the given networks to a compressed domain where they are summarized using fewer nodes, termed supernodes, and interactions. In the second phase, we carry out the alignment in the compressed domain using an existing network alignment method as our base algorithm. This alignment results in supernode mappings in the compressed domain, each of which are smaller instances of network alignment problem. In the third phase, we solve each of the instances using the base alignment algorithm to refine the alignment results. We provide a user defined parameter to control the number of compression levels which generally determines the tradeoff between the quality of the alignment versus how fast the algorithm runs. Our experiments on the networks from KEGG pathway database demonstrate that the compression method we propose reduces the sizes of metabolic networks by almost half at each compression level which provides an expected speedup of more than an order of magnitude. We also observe that the alignments obtained by only one level of compression capture the original alignment results with high accuracy. Together, these suggest that our framework results in alignments that are comparable to existing algorithms and can do this with practical resource utilization for large scale networks that existing algorithms could not handle. As an example of our method's performance in practice, the alignment of organism-wide metabolic networks of human (1615 reactions) and mouse (1600 reactions) was performed under three minutes by only using a single level of compression.     

A Systematic Investigation of Computation Models for Predicting Adverse Drug Reactions (ADRs)

Background

Early and accurate identification of adverse drug reactions (ADRs) is critically important for drug development and clinical safety. Computer-aided prediction of ADRs has attracted increasing attention in recent years, and many computational models have been proposed. However, because of the lack of systematic analysis and comparison of the different computational models, there remain limitations in designing more effective algorithms and selecting more useful features. There is therefore an urgent need to review and analyze previous computation models to obtain general conclusions that can provide useful guidance to construct more effective computational models to predict ADRs.

Principal Findings

In the current study, the main work is to compare and analyze the performance of existing computational methods to predict ADRs, by implementing and evaluating additional algorithms that have been earlier used for predicting drug targets. Our results indicated that topological and intrinsic features were complementary to an extent and the Jaccard coefficient had an important and general effect on the prediction of drug-ADR associations. By comparing the structure of each algorithm, final formulas of these algorithms were all converted to linear model in form, based on this finding we propose a new algorithm called the general weighted profile method and it yielded the best overall performance among the algorithms investigated in this paper.

Conclusion

Several meaningful conclusions and useful findings regarding the prediction of ADRs are provided for selecting optimal features and algorithms.     

Dynamic partitioning for hybrid simulation of the bistable HIV-1 transactivation network

MOTIVATION: The stochastic kinetics of a well-mixed chemical system, governed by the chemical Master equation, can be simulated using the exact methods of Gillespie. However, these methods do not scale well as systems become more complex and larger models are built to include reactions with widely varying rates, since the computational burden of simulation increases with the number of reaction events. Continuous models may provide an approximate solution and are computationally less costly, but they fail to capture the stochastic behavior of small populations of macromolecules. RESULTS: In this article we present a hybrid simulation algorithm that dynamically partitions the system into subsets of continuous and discrete reactions, approximates the continuous reactions deterministically as a system of ordinary differential equations (ODE) and uses a Monte Carlo method for generating discrete reaction events according to a time-dependent propensity. Our approach to partitioning is improved such that we dynamically partition the system of reactions, based on a threshold relative to the distribution of propensities in the discrete subset. We have implemented the hybrid algorithm in an extensible framework, utilizing two rigorous ODE solvers to approximate the continuous reactions, and use an example model to illustrate the accuracy and potential speedup of the algorithm when compared with exact stochastic simulation. AVAILABILITY: Software and benchmark models used for this publication can be made available upon request from the authors.     

Synthesis of peptide aldehydes via enzymatic acylation of amino aldehyde derivatives

Two ways for semi-enzymatic preparation of the peptide aldehydes are proposed: (1) enzymatic acylation of amino alcohols with acyl peptide esters and subsequent chemical oxidation of the resulting peptide alcohols with DMSO/acetic anhydride mixture or (2) enzymatic acylation of the preliminarily obtained by a chemical route amino aldehyde semicarbazones. Subtilisin 72, serine proteinase with a broad specificity, distributed over macroporous silica, was used as a catalyst in both cases. Due to the practical absence of water in the reaction mixtures the yields of the products in both enzymatic reactions were nearly quantitative. The second way seems to be more attractive because all chemical stages were carried out with amino acid derivatives, far less valuable compounds than peptide ones. A series of peptide aldehydes of general formula Z-Ala-Ala-Xaa-al (where Xaa-al=leucinal, phenylalaninal, alaninal, valinal) was obtained. The inhibition parameters for these compounds, in the hydrolysis reactions of corresponding chromogenic substrates for subtilisin and -chymotrypsin, were determined.     

An efficient algorithm for DNA fragment assembly in MapReduce

Fragment assembly is one of the most important problems of sequence assembly. Algorithms for DNA fragment assembly using de Bruijn graph have been widely used. These algorithms require a large amount of memory and running time to build the de Bruijn graph. Another drawback of the conventional de Bruijn approach is the loss of information. To overcome these shortcomings, this paper proposes a parallel strategy to construct de Bruijin graph. Its main characteristic is to avoid the division of de Bruijin graph. A novel fragment assembly algorithm based on our parallel strategy is implemented in the MapReduce framework. The experimental results show that the parallel strategy can effectively improve the computational efficiency and remove the memory limitations of the assembly algorithm based on Euler superpath. This paper provides a useful attempt to the assembly of large-scale genome sequence using Cloud Computing.     

Exploiting drug-disease relationships for computational drug repositioning

Finding new uses for existing drugs, or drug repositioning, has been used as a strategy for decades to get drugs to more patients. As the ability to measure molecules in high-throughput ways has improved over the past decade, it is logical that such data might be useful for enabling drug repositioning through computational methods. Many computational predictions for new indications have been borne out in cellular model systems, though extensive animal model and clinical trial-based validation are still pending. In this review, we show that computational methods for drug repositioning can be classified in two axes: drug based, where discovery initiates from the chemical perspective, or disease based, where discovery initiates from the clinical perspective of disease or its pathology. Newer algorithms for computational drug repositioning will likely span these two axes, will take advantage of newer types of molecular measurements, and will certainly play a role in reducing the global burden of disease.     

Chemical Reaction Networks’ Programming for Solving Equations

The computational ability of the chemical reaction networks (CRNs) using DNA as the substrate has been verified previously. To solve more complex computational problems and perform the computational steps as expected, the practical design of the basic modules of calculation and the steps in the reactions have become the basic requirements for biomolecular computing. This paper presents a method for solving nonlinear equations in the CRNs with DNA as the substrate. We used the basic calculation module of the CRNs with a gateless structure to design discrete and analog algorithms and realized the nonlinear equations that could not be solved in the previous work, such as exponential, logarithmic, and simple triangle equations. The solution of the equation uses the transformation method, Taylor expansion, and Newton iteration method, and the simulation verified this through examples. We used and improved the basic calculation module of the CRN++ programming language, optimized the error in the basic module, and analyzed the error’s variation over time.     

Graph-theoretic methods for the analysis of chemical and biochemical networks. I. Multistability and oscillations in ordinary differential equation models

A chemical mechanism is a model of a chemical reaction network consisting of a set of elementary reactions that express how molecules react with each other. In classical mass-action kinetics, a mechanism implies a set of ordinary differential equations (ODEs) which govern the time evolution of the concentrations. In this article, ODE models of chemical kinetics that have the potential for multiple positive equilibria or oscillations are studied. We begin by considering some methods of stability analysis based on the digraph of the Jacobian matrix. We then prove two theorems originally given by A. N. Ivanova which correlate the bifurcation structure of a mass-action model to the properties of a bipartite graph with nodes representing chemical species and reactions. We provide several examples of the application of these theorems.     

High-throughput inference of protein-protein interfaces from unassigned NMR data

SUMMARY: We cast the problem of identifying protein-protein interfaces, using only unassigned NMR spectra, into a geometric clustering problem. Identifying protein-protein interfaces is critical to understanding inter- and intra-cellular communication, and NMR allows the study of protein interaction in solution. However it is often the case that NMR studies of a protein complex are very time-consuming, mainly due to the bottleneck in assigning the chemical shifts, even if the apo structures of the constituent proteins are known. We study whether it is possible, in a high-throughput manner, to identify the interface region of a protein complex using only unassigned chemical shifts and residual dipolar coupling (RDC) data. We introduce a geometric optimization problem where we must cluster the cells in an arrangement on the boundary of a 3-manifold, where the arrangement is induced by a spherical quadratic form [corrected] The arrangement is induced by a spherical quadratic form, which in turn is parameterized by a SO(3)xR2. We show that this formalism derives directly from the physics of RDCs. We present an optimal algorithm for this problem that runs in O(n3 log n) time for an n-residue protein. We then use this clustering algorithm as a subroutine in a practical algorithm for identifying the interface region of a protein complex from unassigned NMR data. We present the results of our algorithm on NMR data for seven proteins from five protein complexes, and show that our approach is useful for high-throughput applications in which we seek to rapidly identify the interface region of a protein complex. AVAILABILITY: Contact authors for source code.     

Kinetic modeling and fitting software for interconnected reaction schemes: VisKin

Reaction kinetics for complex, highly interconnected kinetic schemes are modeled using analytical solutions to a system of ordinary differential equations. The algorithm employs standard linear algebra methods that are implemented using MatLab functions in a Visual Basic interface. A graphical user interface for simple entry of reaction schemes facilitates comparison of a variety of reaction schemes. To ensure microscopic balance, graph theory algorithms are used to determine violations of thermodynamic cycle constraints. Analytical solutions based on linear differential equations result in fast comparisons of first order kinetic rates and amplitudes as a function of changing ligand concentrations. For analysis of higher order kinetics, we also implemented a solution using numerical integration. To determine rate constants from experimental data, fitting algorithms that adjust rate constants to fit the model to imported data were implemented using the Levenberg-Marquardt algorithm or using Broyden-Fletcher-Goldfarb-Shanno methods. We have included the ability to carry out global fitting of data sets obtained at varying ligand concentrations. These tools are combined in a single package, which we have dubbed VisKin, to guide and analyze kinetic experiments. The software is available online for use on PCs.