Optimized Null Model for Protein Structure Networks

Much attention has recently been given to the statistical significance of topological features observed in biological networks. Here, we consider residue interaction graphs (RIGs) as network representations of protein structures with residues as nodes and inter-residue interactions as edges. Degree-preserving randomized models have been widely used for this purpose in biomolecular networks. However, such a single summary statistic of a network may not be detailed enough to capture the complex topological characteristics of protein structures and their network counterparts. Here, we investigate a variety of topological properties of RIGs to find a well fitting network null model for them. The RIGs are derived from a structurally diverse protein data set at various distance cut-offs and for different groups of interacting atoms. We compare the network structure of RIGs to several random graph models. We show that 3-dimensional geometric random graphs, that model spatial relationships between objects, provide the best fit to RIGs. We investigate the relationship between the strength of the fit and various protein structural features. We show that the fit depends on protein size, structural class, and thermostability, but not on quaternary structure. We apply our model to the identification of significantly over-represented structural building blocks, i.e., network motifs, in protein structure networks. As expected, choosing geometric graphs as a null model results in the most specific identification of motifs. Our geometric random graph model may facilitate further graph-based studies of protein conformation space and have important implications for protein structure comparison and prediction. The choice of a well-fitting null model is crucial for finding structural motifs that play an important role in protein folding, stability and function. To our knowledge, this is the first study that addresses the challenge of finding an optimized null model for RIGs, by comparing various RIG definitions against a series of network models.     

Graph-theoretical assignment of secondary structure in multidimensional protein NMR spectra: Application to the lac repressor headpiece

Summary A novel procedure is presented for the automatic identification of secondary structures in proteins from their corresponding NOE data. The method uses a branch of mathematics known as graph theory to identify prescribed NOE connectivity patterns characteristic of the regular secondary structures. Resonance assignment is achieved by connecting these patterns of secondary structure together, thereby matching the connected spin systems to specific segments of the protein sequence. The method known as SERENDIPITY refers to a set of routines developed in a modular fashion, where each program has one or several well-defined tasks. NOE templates for several secondary structure motifs have been developed and the method has been successfully applied to data obtained from NOESY-type spectra. The present report describes the application of the SERENDIPITY protocol to a 3D NOESY-HMQC spectrum of the ¹⁵N-labelled lac repressor headpiece protein. The application demonstrates that, under favourable conditions, fully automated identification of secondary structures and semi-automated assignment are feasible.Abbreviations 2D, 3D two-, three-dimensional - NOESY nuclear Overhauser enhancement spectroscopy - HMQC heteronuclear multiple quantum coherence - SSE secondary structure element - SERENDIPITY SEcondary structuRE ideNtification in multiDImensional ProteIn specTra analYsis Supplementary Material available from the authors: Two tables containing the total number of mappings resulting from the graph search procedure for simulated and experimental NOE data.     

Protein complexes identification based on go attributed network embedding

Background

Identifying protein complexes from protein-protein interaction (PPI) network is one of the most important tasks in proteomics. Existing computational methods try to incorporate a variety of biological evidences to enhance the quality of predicted complexes. However, it is still a challenge to integrate different types of biological information into the complexes discovery process under a unified framework. Recently, attributed network embedding methods have be proved to be remarkably effective in generating vector representations for nodes in the network. In the transformed vector space, both the topological proximity and node attributed affinity between different nodes are preserved. Therefore, such attributed network embedding methods provide us a unified framework to integrate various biological evidences into the protein complexes identification process.

Results

In this article, we propose a new method called GANE to predict protein complexes based on Gene Ontology (GO) attributed network embedding. Firstly, it learns the vector representation for each protein from a GO attributed PPI network. Based on the pair-wise vector representation similarity, a weighted adjacency matrix is constructed. Secondly, it uses the clique mining method to generate candidate cores. Consequently, seed cores are obtained by ranking candidate cores based on their densities on the weighted adjacency matrix and removing redundant cores. For each seed core, its attachments are the proteins with correlation score that is larger than a given threshold. The combination of a seed core and its attachment proteins is reported as a predicted protein complex by the GANE algorithm. For performance evaluation, we compared GANE with six protein complex identification methods on five yeast PPI networks. Experimental results showes that GANE performs better than the competing algorithms in terms of different evaluation metrics.

Conclusions

GANE provides a framework that integrate many valuable and different biological information into the task of protein complex identification. The protein vector representation learned from our attributed PPI network can also be used in other tasks, such as PPI prediction and disease gene prediction.

     

Discovering protein complexes in protein interaction networks via exploring the weak ties effect

Background

Studying protein complexes is very important in biological processes since it helps reveal the structure-functionality relationships in biological networks and much attention has been paid to accurately predict protein complexes from the increasing amount of protein-protein interaction (PPI) data. Most of the available algorithms are based on the assumption that dense subgraphs correspond to complexes, failing to take into account the inherence organization within protein complex and the roles of edges. Thus, there is a critical need to investigate the possibility of discovering protein complexes using the topological information hidden in edges.

Results

To provide an investigation of the roles of edges in PPI networks, we show that the edges connecting less similar vertices in topology are more significant in maintaining the global connectivity, indicating the weak ties phenomenon in PPI networks. We further demonstrate that there is a negative relation between the weak tie strength and the topological similarity. By using the bridges, a reliable virtual network is constructed, in which each maximal clique corresponds to the core of a complex. By this notion, the detection of the protein complexes is transformed into a classic all-clique problem. A novel core-attachment based method is developed, which detects the cores and attachments, respectively. A comprehensive comparison among the existing algorithms and our algorithm has been made by comparing the predicted complexes against benchmark complexes.

Conclusions

We proved that the weak tie effect exists in the PPI network and demonstrated that the density is insufficient to characterize the topological structure of protein complexes. Furthermore, the experimental results on the yeast PPI network show that the proposed method outperforms the state-of-the-art algorithms. The analysis of detected modules by the present algorithm suggests that most of these modules have well biological significance in context of complexes, suggesting that the roles of edges are critical in discovering protein complexes.

     

In vivo application of photocleavable protein interaction reporter technology

In vivo protein structures and protein-protein interactions are critical to the function of proteins in biological systems. As a complementary approach to traditional protein interaction identification methods, cross-linking strategies are beginning to provide additional data on protein and protein complex topological features. Previously, photocleavable protein interaction reporter (pcPIR) technology was demonstrated by cross-linking pure proteins and protein complexes and the use of ultraviolet light to cleave or release cross-linked peptides to enable identification. In the present report, the pcPIR strategy is applied to Escherichia coli cells, and in vivo protein interactions and topologies are measured. More than 1600 labeled peptides from E. coli were identified, indicating that many protein sites react with pcPIR in vivo. From those labeled sites, 53 in vivo intercross-linked peptide pairs were identified and manually validated. Approximately half of the interactions have been reported using other techniques, although detailed structures exist for very few. Three proteins or protein complexes with detailed crystallography structures are compared to the cross-linking results obtained from in vivo application of pcPIR technology.     

Building retinal connectomes

Understanding vertebrate vision depends on knowing, in part, the complete network graph of at least one representative retina. Acquiring such graphs is the business of synaptic connectomics, emerging as a practical technology due to improvements in electron imaging platform control, management software for large-scale datasets, and availability of data storage. The optimal strategy for building complete connectomes uses transmission electron imaging with 2nm or better resolution, molecular tags for cell identification, open-access data volumes for navigation, and annotation with open-source tools to build 3D cell libraries, complete network diagrams and connectivity databases. The first forays into retinal connectomics have shown that even nominally well-studied cells have much richer connection graphs than expected.     

Peeling the yeast protein network

A set of highly connected proteins (or hubs) plays an important role for the integrity of the protein interaction network of Saccharomyces cerevisae by connecting the network's intrinsic modules. The importance of the hubs' central placement is further confirmed by their propensity to be lethal. However, although highly emphasized, little is known about the topological coherence among the hubs. Applying a core decomposition method which allows us to identify the inherent layer structure of the protein interaction network, we find that the probability of nodes both being essential and evolutionary conserved successively increases toward the innermost cores. While connectivity alone is often not a sufficient criterion to assess a protein's functional, evolutionary and topological relevance, we classify nodes as globally and locally central depending on their appearance in the inner or outer cores. The observation that globally central proteins participate in a substantial number of protein complexes which display an elevated degree of evolutionary conservation allows us to hypothesize that globally central proteins serve as the evolutionary backbone of the proteome. Even though protein interaction data are extensively flawed, we find that our results are very robust against inaccurately determined protein interactions.     

Perspective: network-guided pattern formation of neural dynamics

The understanding of neural activity patterns is fundamentally linked to an understanding of how the brain''s network architecture shapes dynamical processes. Established approaches rely mostly on deviations of a given network from certain classes of random graphs. Hypotheses about the supposed role of prominent topological features (for instance, the roles of modularity, network motifs or hierarchical network organization) are derived from these deviations. An alternative strategy could be to study deviations of network architectures from regular graphs (rings and lattices) and consider the implications of such deviations for self-organized dynamic patterns on the network. Following this strategy, we draw on the theory of spatio-temporal pattern formation and propose a novel perspective for analysing dynamics on networks, by evaluating how the self-organized dynamics are confined by network architecture to a small set of permissible collective states. In particular, we discuss the role of prominent topological features of brain connectivity, such as hubs, modules and hierarchy, in shaping activity patterns. We illustrate the notion of network-guided pattern formation with numerical simulations and outline how it can facilitate the understanding of neural dynamics.     

Modularity in the evolution of yeast protein interaction network

Protein interaction networks are known to exhibit remarkable structures: scale-free and small-world and modular structures. To explain the evolutionary processes of protein interaction networks possessing scale-free and small-world structures, preferential attachment and duplication-divergence models have been proposed as mathematical models. Protein interaction networks are also known to exhibit another remarkable structural characteristic, modular structure. How the protein interaction networks became to exhibit modularity in their evolution? Here, we propose a hypothesis of modularity in the evolution of yeast protein interaction network based on molecular evolutionary evidence. We assigned yeast proteins into six evolutionary ages by constructing a phylogenetic profile. We found that all the almost half of hub proteins are evolutionarily new. Examining the evolutionary processes of protein complexes, functional modules and topological modules, we also found that member proteins of these modules tend to appear in one or two evolutionary ages. Moreover, proteins in protein complexes and topological modules show significantly low evolutionary rates than those not in these modules. Our results suggest a hypothesis of modularity in the evolution of yeast protein interaction network as systems evolution.     

Topological determinants of protein unfolding rates

For proteins that fold by two-state kinetics, the folding and unfolding processes are believed to be closely related to their native structures. In particular, folding and unfolding rates are influenced by the native structures of proteins. Thus, we focus on finding important topological quantities from a protein structure that determine its unfolding rate. After constructing graphs from protein native structures, we investigate the relationships between unfolding rates and various topological quantities of the graphs. First, we find that the correlation between the unfolding rate and the contact order is not as prominent as in the case of the folding rate and the contact order. Next, we investigate the correlation between the unfolding rate and the clustering coefficient of the graph of a protein native structure, and observe no correlation between them. Finally, we find that a newly introduced quantity, the impact of edge removal per residue, has a good overall correlation with protein unfolding rates. The impact of edge removal is defined as the ratio of the change of the average path length to the edge removal probability. From these facts, we conclude that the protein unfolding process is closely related to the protein native structure.     

Integrating Ion Mobility Mass Spectrometry with Molecular Modelling to Determine the Architecture of Multiprotein Complexes

Current challenges in the field of structural genomics point to the need for new tools and technologies for obtaining structures of macromolecular protein complexes. Here, we present an integrative computational method that uses molecular modelling, ion mobility-mass spectrometry (IM-MS) and incomplete atomic structures, usually from X-ray crystallography, to generate models of the subunit architecture of protein complexes. We begin by analyzing protein complexes using IM-MS, and by taking measurements of both intact complexes and sub-complexes that are generated in solution. We then examine available high resolution structural data and use a suite of computational methods to account for missing residues at the subunit and/or domain level. High-order complexes and sub-complexes are then constructed that conform to distance and connectivity constraints imposed by IM-MS data. We illustrate our method by applying it to multimeric protein complexes within the Escherichia coli replisome: the sliding clamp, (β₂), the γ complex (γ₃δδ′), the DnaB helicase (DnaB₆) and the Single-Stranded Binding Protein (SSB₄).     

Problems of structural and functional identification of biological tissues

Theoretical methods for identification of topological and functional parameters of biological tissues (e.g., myocardium) are considered. Unknown topological parameters include the network dimension and connectivity, while unknown functional parameters include the resistivity of the cellular membrane and cytoplasm. The cell size (length and diameter), the input resistance of the tissue, and the fundamental electric potential field formed by a “point” current source (intracellular microelectrode) are treated as experimentally known parameters.     

Problems of structural and functional identification of biological tissues

The theoretical methods of identification of topological and functional parameters for biological tissues, such as myocardium, are considered. Among the unknown topological parameters are the dimension and connectivity of a network, and the unknown functional parameters include the electrical resistance of the cellular membrane and cytoplasm. Experimentally known data are the sizes of cells (length and diameter), the input resistance of tissue, and also the field of electrical potential formed by a "dot" current source (by an intracellular microelectrode).     

Tetramer protein complex interface residue pairs prediction with LSTM combined with graph representations

MotivationProtein-protein interactions are important for many biological processes. Theoretical understanding of the structurally determining factors of interaction sites will help to understand the underlying mechanism of protein-protein interactions. Taking advantage of advanced mathematical methods to correctly predict interaction sites will be useful. Although some previous studies have been devoted to the interaction interface of protein monomer and the interface residues between chains of protein dimers, very few studies about the interface residues prediction of protein multimers, including trimers, tetramer and even more monomers in a large protein complex. As we all know, a large number of proteins function with the form of multibody protein complexes. And the complexity of the protein multimers structure causes the difficulty of interface residues prediction on them. So, we hope to build a method for the prediction of protein tetramer interface residue pairs.ResultsHere, we developed a new deep network based on LSTM network combining with graph to predict protein tetramers interaction interface residue pairs. On account of the protein structure data is not the same as the image or video data which is well-arranged matrices, namely the Euclidean Structure mentioned in many researches. Because the Non-Euclidean Structure data can't keep the translation invariance, and we hope to extract some spatial features from this kind of data applying on deep learning, an algorithm combining with graph was developed to predict the interface residue pairs of protein interactions based on a topological graph building a relationship between vertexes and edges in graph theory combining multilayer Long Short-Term Memory network. First, selecting the training and test samples from the Protein Data Bank, and then extracting the physicochemical property features and the geometric features of surface residue associated with interfacial properties. Subsequently, we transform the protein multimers data to topological graphs and predict protein interaction interface residue pairs using the model. In addition, different types of evaluation indicators verified its validity.     

Computational Methods Toward Unbiased Pattern Mining and Structure Determination in Cryo-Electron Tomography Data

Cryo-electron tomography can uniquely probe the native cellular environment for macromolecular structures. Tomograms feature complex data with densities of diverse, densely crowded macromolecular complexes, low signal-to-noise, and artifacts such as the missing wedge effect. Post-processing of this data generally involves isolating regions or particles of interest from tomograms, organizing them into related groups, and rendering final structures through subtomogram averaging. Template-matching and reference-based structure determination are popular analysis methods but are vulnerable to biases and can often require significant user input. Most importantly, these approaches cannot identify novel complexes that reside within the imaged cellular environment. To reliably extract and resolve structures of interest, efficient and unbiased approaches are therefore of great value. This review highlights notable computational software and discusses how they contribute to making automated structural pattern discovery a possibility. Perspectives emphasizing the importance of features for user-friendliness and accessibility are also presented.     

Role of structural inhomogeneities in resting-state brain dynamics

Brain imaging methods allow a non-invasive assessment of both structural and functional connectivity. However, the mechanism of how functional connectivity arises in a structured network of interacting neural populations is as yet poorly understood. Here we use a modeling approach to explore the way in which functional correlations arise from underlying structural connections taking into account inhomogeneities in the interactions between the brain regions of interest. The local dynamics of a neural population is assumed to be of phase-oscillator type. The considered structural connectivity patterns describe long-range anatomical connections between interacting neural elements. We find a dependence of the simulated functional connectivity patterns on the parameters governing the dynamics. We calculate graph-theoretic measures of the functional network topology obtained from numerical simulations. The effect of structural inhomogeneities in the coupling term on the observed network state is quantified by examining the relation between simulated and empirical functional connectivity. Importantly, we show that simulated and empirical functional connectivity agree for a narrow range of coupling strengths. We conclude that identification of functional connectivity during rest requires an analysis of the network dynamics.