Assembly rules for protein networks derived from phylogenetic-statistical analysis of whole genomes

Background: We report an analysis of a protein network of functionally linked proteins, identified from a phylogenetic statistical analysis of complete eukaryotic genomes. Phylogenetic methods identify pairs of proteins that co-evolve on a phylogenetic tree, and have been shown to have a high probability of correctly identifying known functional links. Results: The eukaryotic correlated evolution network we derive displays the familiar power law scaling of connectivity. We introduce the use of explicit phylogenetic methods to reconstruct the ancestral presence or absence of proteins at the interior nodes of a phylogeny of eukaryote species. We find that the connectivity distribution of proteins at the point they arise on the tree and join the network follows a power law, as does the connectivity distribution of proteins at the time they are lost from the network. Proteins resident in the network acquire connections over time, but we find no evidence that 'preferential attachment' - the phenomenon of newly acquired connections in the network being more likely to be made to proteins with large numbers of connections - influences the network structure. We derive a 'variable rate of attachment' model in which proteins vary in their propensity to form network interactions independently of how many connections they have or of the total number of connections in the network, and show how this model can produce apparent power-law scaling without preferential attachment. Conclusion: A few simple rules can explain the topological structure and evolutionary changes to protein-interaction networks: most change is concentrated in satellite proteins of low connectivity and small phenotypic effect, and proteins differ in their propensity to form attachments. Given these rules of assembly, power law scaled networks naturally emerge from simple principles of selection, yielding protein interaction networks that retain a high-degree of robustness on short time scales and evolvability on longer evolutionary time scales.

Interaction with calmodulin is important for the secretion of thimet oligopeptidase following stimulation

Thimet oligopeptidase (EC 3.4.24.15; EP24.15) was originally described as a neuropeptide-metabolizing enzyme, highly expressed in the brain, kidneys and neuroendocrine tissue. EP24.15 lacks a typical signal peptide sequence for entry into the secretory pathway and is secreted by cells via an unconventional and unknown mechanism. In this study, we identified a novel calcium-dependent interaction between EP24.15 and calmodulin, which is important for the stimulated, but not constitutive, secretion of EP24.15. We demonstrated that, in vitro, EP24.15 and calmodulin physically interact only in the presence of Ca(2+), with an estimated K(d) value of 0.52 mu m. Confocal microscopy confirmed that EP24.15 colocalizes with calmodulin in the cytosol of resting HEK293 cells. This colocalization markedly increases when cells are treated with either the calcium ionophore A23187 or the protein kinase A activator forskolin. Overexpression of calmodulin in HEK293 cells is sufficient to greatly increase the A23187-stimulated secretion of EP24.15, which can be inhibited by the calmodulin inhibitor calmidazolium. The specific inhibition of protein kinase A with KT5720 reduces the A23187-stimulated secretion of EP24.15 and inhibits the synergistic effects of forskolin with A23187. Treatment with calmidazolium and KT5720 nearly abolishes the stimulatory effects of A23187 on EP24.15 secretion. Together, these data suggest that the interaction between EP24.15 and calmodulin is regulated within cells and is important for the stimulated secretion of EP24.15 from HEK293 cells.

Protein lethality investigated in terms of long range dynamical interactions

The relationship between network structure/dynamics and biological function constitutes a fundamental issue in systems biology. However, despite many related investigations, the correspondence between structure and biological functions is not yet fully understood. A related subject that has deserved particular attention recently concerns how essentiality is related to the structure and dynamics of protein interactions. In the current work, protein essentiality is investigated in terms of long range influences in protein-protein interaction networks by considering simulated dynamical aspects. This analysis is performed with respect to outward activations, an approach which models the propagation of interactions between proteins by considering self-avoiding random walks. The obtained results are compared to protein local connectivity. Both the connectivity and the outward activations were found to be strongly related to protein essentiality.

Cwc24p, a novel Saccharomyces cerevisiae nuclear ring finger protein, affects pre-snoRNA U3 splicing

U3 snoRNA is transcribed from two intron-containing genes in yeast, snR17A and snR17B. Although the assembly of the U3 snoRNP has not been precisely determined, at least some of the core box C/D proteins are known to bind pre-U3 co-transcriptionally, thereby affecting splicing and 3 `-end processing of this snoRNA. We identified the interaction between the box C/D assembly factor Nop17p and Cwc24p, a novel yeast RING finger protein that had been previously isolated in a complex with the splicing factor Cef1p. Here we show that, consistent with the protein interaction data, Cwc24p localizes to the cell nucleus, and its depletion leads to the accumulation of both U3 pre-snoRNAs. U3 snoRNA is involved in the early cleavages of 35 S pre-rRNA, and the defective splicing of pre-U3 detected in cells depleted of Cwc24p causes the accumulation of the 35 S precursor rRNA. These results led us to the conclusion that Cwc 24p is involved in pre-U3 snoRNA splicing, indirectly affecting pre-rRNA processing.

Sdo1p, the yeast orthologue of Shwachman-Bodian-Diamond syndrome protein, binds RNA and interacts with nuclear rRNA-processing factors

The Shwachman-Bodian-Diamond syndrome protein (SBDS) is a member of a highly conserved protein family of not well understood function, with putative orthologues found in different organisms ranging from Archaea, yeast and plants to vertebrate animals. The yeast orthologue of SBDS, Sdo1p, has been previously identified in association with the 60S ribosomal subunit and is proposed to participate in ribosomal recycling. Here we show that Sdo1p interacts with nucleolar rRNA processing factors and ribosomal proteins, indicating that it might bind the pre-60S complex and remain associated with it during processing and transport to the cytoplasm. Corroborating the protein interaction data, Sdo1p localizes to the nucleus and cytoplasm and co-immunoprecipitates precursors of 60S and 40S subunits, as well as the mature rRNAs. Sdo1p binds RNA directly, suggesting that it may associate with the ribosomal subunits also through RNA interaction. Copyright (C) 2009 John Wiley & Sons, Ltd.

Human regulatory protein Ki-1/57 has characteristics of an intrinsically unstructured protein

The human protein Ki-1/57 was first identified through the cross reactivity of the anti-CD30 monoclonal antibody Ki-1; in Hodgkin lymphoma cells. The expression of Ki-1/57 in diverse cancer cells and its phosphorylation in peripheral blood leukocytes after mitogenic activation suggested its possible role in cell signaling. Ki-1/57 interacts with several other regulatory proteins involved in cellular signaling, transcriptional regulation and RNA metabolism, suggesting it may have pleiotropic functions. In a previous spectroscopic analysis, we observed a low content of secondary structure for Ki-1/57 constructs. Here, Circular dichroism experiments, in vitro RNA binding analysis, and limited proteolysis assays of recombinant Ki-1/57(122-413) and proteolysis assays of endogenous full length protein from human HEK293 cells suggested that Ki-1/57 has characteristics of an intrinsically unstructured protein. Small-angle X-ray scattering (SAXS) experiments were performed with the C-terminal fragment Ki-1/57(122-413). These results indicated an elongated shape and a partially unstructured conformation of the molecule in solution, confirming the characteristics of an intrinsically unstructured protein. Experimental curves together with ab initio modeling approaches revealed an extended and flexible molecule in solution. An elongated shape was also observed by analytical gel filtration. Furthermore, sedimentation velocity analysis suggested that Ki-1/57 is a highly asymmetric protein. These findings may explain the functional plasticity of Ki-1/57, as suggested by the wide array of proteins with which it is capable of interacting in yeast two-hybrid interaction assays.

Semantic and layered protein function prediction from PPI networks

Background The past few years have seen a rapid development in novel high-throughput technologies that have created large-scale data on protein-protein interactions (PPI) across human and most model species. This data is commonly represented as networks, with nodes representing proteins and edges representing the PPIs. A fundamental challenge to bioinformatics is how to interpret this wealth of data to elucidate the interaction of patterns and the biological characteristics of the proteins. One significant purpose of this interpretation is to predict unknown protein functions. Although many approaches have been proposed in recent years, the challenge still remains how to reasonably and precisely measure the functional similarities between proteins to improve the prediction effectiveness.

Results We used a Semantic and Layered Protein Function Prediction (SLPFP) framework to more effectively predict unknown protein functions at different functional levels. The framework relies on a new protein similarity measurement and a clustering-based protein function prediction algorithm. The new protein similarity measurement incorporates the topological structure of the PPI network, as well as the protein's semantic information in terms of known protein functions at different functional layers. Experiments on real PPI datasets were conducted to evaluate the effectiveness of the proposed framework in predicting unknown protein functions.

Conclusion The proposed framework has a higher prediction accuracy compared with other similar approaches. The prediction results are stable even for a large number of proteins. Furthermore, the framework is able to predict unknown functions at different functional layers within the Munich Information Center for Protein Sequence (MIPS) hierarchical functional scheme. The experimental results demonstrated that the new protein similarity measurement reflects more reasonably and precisely relationships between proteins.

Advanced graph mining methods for protein analysis

As one of the primary substances in a living organism, protein defines the character of each cell by interacting with the cellular environment to promote the cell’s growth and function [1]. Previous studies on proteomics indicate that the functions of different proteins could be assigned based upon protein structures [2,3]. The knowledge on protein structures gives us an overview of protein fold space and is helpful for the understanding of the evolutionary principles behind structure. By observing the architectures and topologies of the protein families, biological processes can be investigated more directly with much higher resolution and finer detail. For this reason, the analysis of protein, its structure and the interaction with the other materials is emerging as an important problem in bioinformatics. However, the determination of protein structures is experimentally expensive and time consuming, this makes scientists largely dependent on sequence rather than more general structure to infer the function of the protein at the present time. For this reason, data mining technology is introduced into this area to provide more efficient data processing and knowledge discovery approaches.

Unlike many data mining applications which lack available data, the protein structure determination problem and its interaction study, on the contrary, could utilize a vast amount of biologically relevant information on protein and its interaction, such as the protein data bank (PDB) [4], the structural classification of proteins (SCOP) databases [5], CATH databases [6], UniProt [7], and others. The difficulty of predicting protein structures, specially its 3D structures, and the interactions between proteins as shown in Figure 6.1, lies in the computational complexity of the data. Although a large number of approaches have been developed to determine the protein structures such as ab initio modelling [8], homology modelling [9] and threading [10], more efficient and reliable methods are still greatly needed.

In this chapter, we will introduce a state-of-the-art data mining technique, graph mining, which is good at defining and discovering interesting structural patterns in graphical data sets, and take advantage of its expressive power to study protein structures, including protein structure prediction and comparison, and protein-protein interaction (PPI). The current graph pattern mining methods will be described, and typical algorithms will be presented, together with their applications in the protein structure analysis.

The rest of the chapter is organized as follows: Section 6.2 will give a brief introduction of the fundamental knowledge of protein, the publicly accessible protein data resources and the current research status of protein analysis; in Section 6.3, we will pay attention to one of the state-of-the-art data mining methods, graph mining; then Section 6.4 surveys several existing work for protein structure analysis using advanced graph mining methods in the recent decade; finally, in Section 6.5, a conclusion with potential further work will be summarized.

An iterative approach of protein function prediction

Background: Current approaches of predicting protein functions from a protein-protein interaction (PPI) dataset are based on an assumption that the available functions of the proteins (a.k.a. annotated proteins) will determine the functions of the proteins whose functions are unknown yet at the moment (a.k.a. un-annotated proteins). Therefore, the protein function prediction is a mono-directed and one-off procedure, i.e. from annotated proteins to un-annotated proteins. However, the interactions between proteins are mutual rather than static and mono-directed, although functions of some proteins are unknown for some reasons at present. That means when we use the similarity-based approach to predict functions of un-annotated proteins, the un-annotated proteins, once their functions are predicted, will affect the similarities between proteins, which in turn will affect the prediction results. In other words, the function prediction is a dynamic and mutual procedure. This dynamic feature of protein interactions, however, was not considered in the existing prediction algorithms.

Results: In this paper, we propose a new prediction approach that predicts protein functions iteratively. This iterative approach incorporates the dynamic and mutual features of PPI interactions, as well as the local and global semantic influence of protein functions, into the prediction. To guarantee predicting functions iteratively, we propose a new protein similarity from protein functions. We adapt new evaluation metrics to evaluate the prediction quality of our algorithm and other similar algorithms. Experiments on real PPI datasets were conducted to evaluate the effectiveness of the proposed approach in predicting unknown protein functions.

Conclusions: The iterative approach is more likely to reflect the real biological nature between proteins when predicting functions. A proper definition of protein similarity from protein functions is the key to predicting functions iteratively. The evaluation results demonstrated that in most cases, the iterative approach outperformed non-iterative ones with higher prediction quality in terms of prediction precision, recall and F-value.

Predicting protein functions from PPI networks using functional aggregation

Predicting protein functions computationally from massive protein–protein interaction (PPI) data generated by high-throughput technology is one of the challenges and fundamental problems in the post-genomic era. Although there have been many approaches developed for computationally predicting protein functions, the mutual correlations among proteins in terms of protein functions have not been thoroughly investigated and incorporated into existing prediction methods, especially in voting based prediction methods. In this paper, we propose an innovative method to predict protein functions from PPI data by aggregating the functional correlations among relevant proteins using the Choquet-Integral in fuzzy theory. This functional aggregation measures the real impact of each relevant protein function on the final prediction results, and reduces the impact of repeated functional information on the prediction. Accordingly, a new protein similarity and a new iterative prediction algorithm are proposed in this paper. The experimental evaluations on real PPI datasets demonstrate the effectiveness of our method.

Iteratively predict protein functions from protein-protein interactions

Current similarity-based approaches of predicting protein functions from protein-protein interaction (PPI) data usually make use of available information in the PPI network to predict functions of un-annotated proteins, and the prediction is a one-off procedure. However the interactions between proteins are more likely to be mutual rather than static and mono-directed. In other words, the un-annotated proteins, once their functions are predicted, will in turn affect the similarities between proteins. In this paper, we propose an innovative iteration algorithm that incorporates this dynamic feature of protein interaction into the protein function prediction, aiming to achieve higher prediction accuracies and get more reasonable results. With our algorithm, instead of one-off function predictions, functions are assigned to an unannotated protein iteratively until the functional similarities between proteins achieve a stable state. The experimental results show that our iterative method can provide better prediction results than one-off prediction methods with higher prediction accuracies, and is stable for large protein datasets.

Dynamically predicting protein functions from semantic associations of proteins

Predicting functions of un-annotated proteins is a significant challenge in the post-genomics era. Among existing computational approaches, exploiting interactions between proteins to predict functions of un-annotated proteins is widely used. However, it remains difficult to extract semantic associations between proteins (i.e. protein associations in terms of protein functionality) from protein interactions and incorporate extracted semantic associations to more effectively predict protein functions. Furthermore, existing approaches and algorithms regard the function prediction as a one-off procedure, ignoring dynamic and mutual associations between proteins. Therefore, deriving and exploiting semantic associations between proteins to dynamically predict functions are a promising and challenging approach for achieving better prediction results. In this paper, we propose an innovative algorithm to incorporate semantic associations between proteins into a dynamic procedure of protein function prediction. The semantic association between two proteins is measured by the semantic similarity of two proteins which is defined by the similarities of functions two proteins possess. To achieve better prediction results, function similarities are also incorporated into the prediction procedure. The algorithm dynamically predicts functions by iteratively selecting functions for the un-annotated protein and updating the similarities between the un-annotated protein and its neighbour annotated proteins until such suitable functions are selected that the similarities no longer change. The experimental results on real protein interaction datasets demonstrated that our method outperformed the similar and non-dynamic function prediction methods. Incorporating semantic associations between proteins into a dynamic procedure of function prediction reflects intrinsic relationships among proteins as well as dynamic features of protein interactions, and therefore, can significantly improve prediction results.

Dynamically searching for a domain for protein function prediction

The availability of large amounts of protein-protein interaction (PPI) data makes it feasible to use computational approaches to predict protein functions. The base of existing computational approaches is to exploit the known function information of annotated proteins in the PPI data to predict functions of un-annotated proteins. However, these approaches consider the prediction domain (i.e. the set of proteins from which the functions are predicted) as unchangeable during the prediction procedure. This may lead to valuable information being overwhelmed by the unavoidable noise information in the PPI data when predicting protein functions, and in turn, the prediction results will be distorted. In this paper, we propose a novel method to dynamically predict protein functions from the PPI data. Our method regards the function prediction as a dynamic process of finding a suitable prediction domain, from which representative functions of the domain are selected to predict functions of un-annotated proteins. Our method exploits the topological structural information of a PPI network and the semantic relationship between protein functions to measure the relationship between proteins, dynamically select a suitable prediction domain and predict functions. The evaluation on real PPI datasets demonstrated the effectiveness of our proposed method, and generated better prediction results.