Protein complex prediction based on maximum matching with domain–domain interaction

With the development of high-throughput methods for identifying protein–protein interactions, large scale interaction networks are available. Computational methods to analyze the networks to detect functional modules as protein complexes are becoming more important. However, most of the existing methods only make use of the protein–protein interaction networks without considering the structural limitations of proteins to bind together. In this paper, we design a new protein complex prediction method by extending the idea of using domain–domain interaction information. Here we formulate the problem into a maximum matching problem (which can be solved in polynomial time) instead of the binary integer linear programming approach (which can be NP-hard in the worst case). We also add a step to predict domain–domain interactions which first searches the database Pfam using the hidden Markov model and then predicts the domain–domain interactions based on the database DOMINE and InterDom which contain confirmed DDIs. By adding the domain–domain interaction prediction step, we have more edges in the DDI graph and the recall value is increased significantly (at least doubled) comparing with the method of Ozawa et al. (2010) [1] while the average precision value is slightly better. We also combine our method with three other existing methods, such as COACH, MCL and MCODE. Experiments show that the precision of the combined method is improved. This article is part of a Special Issue entitled: Computational Methods for Protein Interaction and Structural Prediction.     

Architecture of basic building blocks in protein and domain structural interaction networks

MOTIVATION: The structural interaction of proteins and their domains in networks is one of the most basic molecular mechanisms for biological cells. Topological analysis of such networks can provide an understanding of and solutions for predicting properties of proteins and their evolution in terms of domains. A single paradigm for the analysis of interactions at different layers, such as domain and protein layers, is needed. RESULTS: Applying a colored vertex graph model, we integrated two basic interaction layers under a unified model: (1) structural domains and (2) their protein/complex networks. We identified four basic and distinct elements in the model that explains protein interactions at the domain level. We searched for motifs in the networks to detect their topological characteristics using a pruning strategy and a hash table for rapid detection. We obtained the following results: first, compared with a random distribution, a substantial part of the protein interactions could be explained by domain-level structural interaction information. Second, there were distinct kinds of protein interaction patterns classified by specific and distinguishable numbers of domains. The intermolecular domain interaction was the most dominant protein interaction pattern. Third, despite the coverage of the protein interaction information differing among species, the similarity of their networks indicated shared architectures of protein interaction network in living organisms. Remarkably, there were only a few basic architectures in the model (>10 for a 4-node network topology), and we propose that most biological combinations of domains into proteins and complexes can be explained by a small number of key topological motifs. CONTACT: doheon@kaist.ac.kr.     

Inferring phenomenological models of first passage processes

Biochemical processes in cells are governed by complex networks of many chemical species interacting stochastically in diverse ways and on different time scales. Constructing microscopically accurate models of such networks is often infeasible. Instead, here we propose a systematic framework for building phenomenological models of such networks from experimental data, focusing on accurately approximating the time it takes to complete the process, the First Passage (FP) time. Our phenomenological models are mixtures of Gamma distributions, which have a natural biophysical interpretation. The complexity of the models is adapted automatically to account for the amount of available data and its temporal resolution. The framework can be used for predicting behavior of FP systems under varying external conditions. To demonstrate the utility of the approach, we build models for the distribution of inter-spike intervals of a morphologically complex neuron, a Purkinje cell, from experimental and simulated data. We demonstrate that the developed models can not only fit the data, but also make nontrivial predictions. We demonstrate that our coarse-grained models provide constraints on more mechanistically accurate models of the involved phenomena.     

A comparative study of cells in inflammation,EAE and MS using biomedical literature data mining

Summary Biomedical literature and database annotations, available in electronic forms, contain a vast amount of knowledge resulting from global research. Users, attempting to utilize the current state-of-the-art research results are frequently overwhelmed by the volume of such information, making it difficult and time-consuming to locate the relevant knowledge. Literature mining, data mining, and domain specific knowledge integration techniques can be effectively used to provide a user-centric view of the information in a real-world biological problem setting. Bioinformatics tools that are based on real-world problems can provide varying levels of information content, bridging the gap between biomedical and bioinformatics research. We have developed a user-centric bioinformatics research tool, called BioMap, that can provide a customized, adaptive view of the information and knowledge space. BioMap was validated by using inflammatory diseases as a problem domain to identify and elucidate the associations among cells and cellular components involved in multiple sclerosis (MS) and its animal model, experimental allergic encephalomyelitis (EAE). The BioMap system was able to demonstrate the associations between cells directly excavated from biomedical literature for inflammation, EAE and MS. These association graphs followed the scale-free network behavior (average γ = 2.1) that are commonly found in biological networks.     

Structure-based systems biology: a zoom lens for the cell

Systems biology seeks to explain complex biological systems, such as the cell, through the integration of many different types of information. Here, we discuss how the incorporation of high-resolution structural data can provide key molecular details often necessary to understand the complex connection between individual molecules and cell behavior. We suggest a process of zooming on the cell, from global networks through pathways to the precise atomic contacts at the interfaces of interacting proteins.     

Simulating the evolution of signal transduction pathways

We use a generic model of a network of proteins that can activate or deactivate each other to explore the emergence and evolution of signal transduction networks and to gain a basic understanding of their general properties. Starting with a set of non-interacting proteins, we evolve a signal transduction network by random mutation and selection to fulfill a complex biological task. In order to validate this approach we base selection on a fitness function that captures the essential features of chemotactic behavior as seen in bacteria. We find that a system of as few as three proteins can evolve into a network mediating chemotaxis-like behavior by acting as a "derivative sensor". Furthermore, we find that the dynamics and topology of such networks show many similarities to the natural chemotaxis pathway, that the response magnitude can increase with increasing network size and that network behavior shows robustness towards variations in some of the internal parameters. We conclude that simulating the evolution of signal transduction networks to mediate a certain behavior may be a promising approach for understanding the general properties of the natural pathway for that behavior.     

Elementary Flux Modes Analysis of Functional Domain Networks Allows a Better Metabolic Pathway Interpretation

Metabolic network analysis is an important step for the functional understanding of biological systems. In these networks, enzymes are made of one or more functional domains often involved in different catalytic activities. Elementary flux mode (EFM) analysis is a method of choice for the topological studies of these enzymatic networks. In this article, we propose to use an EFM approach on networks that encompass available knowledge on structure-function. We introduce a new method that allows to represent the metabolic networks as functional domain networks and provides an application of the algorithm for computing elementary flux modes to analyse them. Any EFM that can be represented using the classical representation can be represented using our functional domain network representation but the fine-grained feature of functional domain networks allows to highlight new connections in EFMs. This methodology is applied to the tricarboxylic acid cycle (TCA cycle) of Bacillus subtilis, and compared to the classical analyses. This new method of analysis of the functional domain network reveals that a specific inhibition on the second domain of the lipoamide dehydrogenase (pdhD) component of pyruvate dehydrogenase complex leads to the loss of all fluxes. Such conclusion was not predictable in the classical approach.     

The Robustness of a Signaling Complex to Domain Rearrangements Facilitates Network Evolution

The rearrangement of protein domains is known to have key roles in the evolution of signaling networks and, consequently, is a major tool used to synthetically rewire networks. However, natural mutational events leading to the creation of proteins with novel domain combinations, such as in frame fusions followed by domain loss, retrotranspositions, or translocations, to name a few, often simultaneously replace pre-existing genes. Thus, while proteins with new domain combinations may establish novel network connections, it is not clear how the concomitant deletions are tolerated. We investigated the mechanisms that enable signaling networks to tolerate domain rearrangement-mediated gene replacements. Using as a model system the yeast mitogen activated protein kinase (MAPK)-mediated mating pathway, we analyzed 92 domain-rearrangement events affecting 11 genes. Our results indicate that, while domain rearrangement events that result in the loss of catalytic activities within the signaling complex are not tolerated, domain rearrangements can drastically alter protein interactions without impairing function. This suggests that signaling complexes can maintain function even when some components are recruited to alternative sites within the complex. Furthermore, we also found that the ability of the complex to tolerate changes in interaction partners does not depend on long disordered linkers that often connect domains. Taken together, our results suggest that some signaling complexes are dynamic ensembles with loose spatial constraints that could be easily re-shaped by evolution and, therefore, are ideal targets for cellular engineering.     

Statecharts for Gene Network Modeling

State diagrams (stategraphs) are suitable for describing the behavior of dynamic systems. However, when they are used to model large and complex systems, determining the states and transitions among them can be overwhelming, due to their flat, unstratified structure. In this article, we present the use of statecharts as a novel way of modeling complex gene networks. Statecharts extend conventional state diagrams with features such as nested hierarchy, recursion, and concurrency. These features are commonly utilized in engineering for designing complex systems and can enable us to model complex gene networks in an efficient and systematic way. We modeled five key gene network motifs, simple regulation, autoregulation, feed-forward loop, single-input module, and dense overlapping regulon, using statecharts. Specifically, utilizing nested hierarchy and recursion, we were able to model a complex interlocked feed-forward loop network in a highly structured way, demonstrating the potential of our approach for modeling large and complex gene networks.     

De Novo Evolution of Complex, Global and Hierarchical Gene Regulatory Mechanisms

Gene regulatory networks exhibit complex, hierarchical features such as global regulation and network motifs. There is much debate about whether the evolutionary origins of such features are the results of adaptation, or the by-products of non-adaptive processes of DNA replication. The lack of availability of gene regulatory networks of ancestor species on evolutionary timescales makes this a particularly difficult problem to resolve. Digital organisms, however, can be used to provide a complete evolutionary record of lineages. We use a biologically realistic evolutionary model that includes gene expression, regulation, metabolism and biosynthesis, to investigate the evolution of complex function in gene regulatory networks. We discover that: (i) network architecture and complexity evolve in response to environmental complexity, (ii) global gene regulation is selected for in complex environments, (iii) complex, inter-connected, hierarchical structures evolve in stages, with energy regulation preceding stress responses, and stress responses preceding growth rate adaptations and (iv) robustness of evolved models to mutations depends on hierarchical level: energy regulation and stress responses tend not to be robust to mutations, whereas growth rate adaptations are more robust and non-lethal when mutated. These results highlight the adaptive and incremental evolution of complex biological networks, and the value and potential of studying realistic in silico evolutionary systems as a way of understanding living systems.     

Small-angle X-ray scattering studies of enzymes

Enzyme function requires conformational changes to achieve substrate binding, domain rearrangements, and interactions with partner proteins, but these movements are difficult to observe. Small-angle X-ray scattering (SAXS) is a versatile structural technique that can probe such conformational changes under solution conditions that are physiologically relevant. Although it is generally considered a low-resolution structural technique, when used to study conformational changes as a function of time, ligand binding, or protein interactions, SAXS can provide rich insight into enzyme behavior, including subtle domain movements. In this perspective, we highlight recent uses of SAXS to probe structural enzyme changes upon ligand and partner-protein binding and discuss tools for signal deconvolution of complex protein solutions.     

Equation discovery for systems biology: finding the structure and dynamics of biological networks from time course data

Reconstructing biological networks, such as metabolic and signaling networks, is at the heart of systems biology. Although many approaches exist for reconstructing network structure, few approaches recover the full dynamic behavior of a network. We survey such approaches that originate from computational scientific discovery, a subfield of machine learning. These take as input measured time course data, as well as existing domain knowledge, such as partial knowledge of the network structure. We demonstrate the use of these approaches on illustrative tasks of finding the complete dynamics of biological networks, which include examples of rediscovering known networks and their dynamics, as well as examples of proposing models for unknown networks.     

Multiscale simulation of actin filaments and actin-associated proteins

Actin is an important cytoskeletal protein that serves as a building block to form filament networks that span across the cell. These networks are orchestrated by a myriad of other cytoskeletal entities including the unbranched filament–forming protein formin and branched network–forming protein complex Arp2/3. Computational models have been able to provide insights into many important structural transitions that are involved in forming these networks, and into the nature of interactions essential for actin filament formation and for regulating the behavior of actin-associated proteins. In this review, we summarize a subset of such models that focus on the atomistic features and those that can integrate atomistic features into a larger picture in a multiscale fashion.     

Structural Mechanism for the Specific Assembly and Activation of the Extracellular Signal Regulated Kinase 5 (ERK5) Module

Mitogen-activated protein kinase (MAPK) activation depends on a linear binding motif found in all MAPK kinases (MKK). In addition, the PB1 (Phox and Bem1) domain of MKK5 is required for extracellular signal regulated kinase 5 (ERK5) activation. We present the crystal structure of ERK5 in complex with an MKK5 construct comprised of the PB1 domain and the linear binding motif. We show that ERK5 has distinct protein-protein interaction surfaces compared with ERK2, which is the closest ERK5 paralog. The two MAPKs have characteristically different physiological functions and their distinct protein-protein interaction surface topography enables them to bind different sets of activators and substrates. Structural and biochemical characterization revealed that the MKK5 PB1 domain cooperates with the MAPK binding linear motif to achieve substrate specific binding, and it also enables co-recruitment of the upstream activating enzyme and the downstream substrate into one signaling competent complex. Studies on present day MAPKs and MKKs hint on the way protein kinase networks may evolve. In particular, they suggest how paralogous enzymes with similar catalytic properties could acquire novel signaling roles by merely changing the way they make physical links to other proteins.     

Probabilistic prediction of unknown metabolic and signal-transduction networks.

Regulatory networks provide control over complex cell behavior in all kingdoms of life. Here we describe a statistical model, based on representing proteins as collections of domains or motifs, which predicts unknown molecular interactions within these biological networks. Using known protein-protein interactions of Saccharomyces cerevisiae as training data, we were able to predict the links within this network with only 7% false-negative and 10% false-positive error rates. We also use Markov chain Monte Carlo simulation for the prediction of networks with maximum probability under our model. This model can be applied across species, where interaction data from one (or several) species can be used to infer interactions in another. In addition, the model is extensible and can be analogously applied to other molecular data (e.g., DNA sequences).