Dominating biological networks

Construction and comprehensive analysis of the biological network related to rheumatoid arthritis-related interstitial lung disease

OBJECTIVE

Interstitial lung disease (ILD) is a severe manifestation of rheumatoid arthritis (RA), which is characterized by low survival time post-diagnosis. Thus, it is important to explore the role of gene regulation related with ILD.

METHOD

Constructed a RA-ILD-related long chain noncoding RNA - messenger RNA (lncRNA-mRNA) network (ILD-LMN), based on ILD- and RA-related genes. We analyzed the topological properties of the resulting network.

RESULT

The results for network modularization and functional analysis showed that ILD-LMN performed basic and specific functions in ILD pathology. Furthermore, differential expression and correlation analysis of hub nodes revealed highly correlated competitive endogenous RNA regulatory relationships with important roles in pathological regulation. Following this, statistical analysis of disease-related single nucleotide polymorphisms (SNPs) in hub lncRNAs revealed that some of transcription factor-related SNPs were significantly associated with the expression of lncRNA. In fact, these SNPs exhibited significant differential expression in disease and normal samples.

CONCLUSION

These results suggest that ILD-LMN has important implications in the study of disease. Altogether, the study of RA- and ILD-related lncRNA and genes on the basis of biological network would assist in providing better treatment opportunities for ILD patients. Additionally, it would promote further research on treatment of the disease.

Supervised Prediction of Aging-Related Genes From a Context-Specific Protein Interaction Subnetwork

Human aging is linked to many prevalent diseases. The aging process is highly influenced by genetic factors. Hence, it is important to identify human aging-related genes. We focus on supervised prediction of such genes. Gene expression-based methods for this purpose study genes in isolation from each other. While protein-protein interaction (PPI) network-based methods for this purpose account for interactions between genes' protein products, current PPI network data are context-unspecific, spanning different biological conditions. Instead, here, we focus on an aging-specific subnetwork of the entire PPI network, obtained by integrating aging-specific gene expression data and PPI network data. The potential of such data integration has been recognized but mostly in the context of cancer. So, we are the first to propose a supervised learning framework for predicting aging-related genes from an aging-specific PPI subnetwork. In a systematic and comprehensive evaluation, we find that in many of the evaluation tests: (i) using an aging-specific subnetwork indeed yields more accurate aging-related gene predictions than using the entire network, and (ii) predictive methods from our framework that have not previously been used for supervised prediction of aging-related genes outperform existing prominent methods for the same purpose. These results justify the need for our framework.

Constraint-based models for dominating protein interaction networks

The minimum dominating set (MDSet) comprises the smallest number of graph nodes, where other graph nodes are connected with at least one MDSet node. The MDSet has been successfully applied to extract proteins that control protein–protein interaction (PPI) networks and to reveal the correlation between structural analysis and biological functions. Although the PPI network contains many MDSets, the identification of multiple MDSets is an NP‐complete problem, and it is difficult to determine the best MDSets, enriched with biological functions. Therefore, the MDSet model needs to be further expanded and validated to find constrained solutions that differ from those generated by the traditional models. Moreover, by identifying the critical set of the network, the set of nodes common to all MDSets can be time‐consuming. Herein, the authors adopted the minimisation of metabolic adjustment (MOMA) algorithm to develop a new framework, called maximisation of interaction adjustment (MOIA). In MOIA, they provide three models; the first one generates two MDSets with a minimum number of shared proteins, the second model generates constrained multiple MDSets (k‐MDSets), and the third model generates user‐defined MDSets, containing the maximum number of essential genes and/or other important genes of the PPI network. In practice, these models significantly reduce the cost of finding the critical set and classifying the graph nodes. Herein, the authors termed the critical set as the k‐critical set, where k is the number of MDSets generated by the proposed model. Then, they defined a new set of proteins called the (k−1)‐critical set, where each node belongs to (k−1) MDSets. This set has been shown to be as important as the k‐critical set and contains many essential genes, transcription factors, and protein kinases as the k‐critical set. The (k−1)‐critical set can be used to extend the search for drug target proteins. Based on the performance of the MOIA models, the authors believe the proposed methods contribute to answering key questions about the MDSets of PPI networks, and their results and analysis can be extended to other network types.

Drug repurposing for hyperlipidemia associated disorders: An integrative network biology and machine learning approach

Hyperlipidemia causes diseases like cardiovascular disease, cancer, Type II Diabetes and Alzheimer's disease. Drugs that specifically target HL associated diseases are required for treatment. 34 KEGG pathways targeted by lipid lowering drugs were used to construct a directed protein-protein interaction network and driver nodes were determined using CytoCtrlAnalyser plugin of Cytoscape 3.6. The involvement of driver nodes of HL in other diseases was verified using GWAS. The central nodes of the network and 34 overrepresented pathways had a critical role in Hyperlipidemia. The PI3K-AKT signalling pathway, non-essentiality, non-centrality and approved drug target status were the predominant features of the driver nodes. Next, a Random Forest classifier was trained on 1445 molecular descriptors calculated using PaDEL for 50 approved lipid lowering and 84 lipid raising drugs as the positive and negative training set respectively. The classifier showed average accuracy of 76.8 % during 5-fold cross validation with AUC of 0.79 ± 0.06 for the ROC curve. The classifier was applied to select molecules with favourable properties for lipid lowering from the 130 approved drugs interacting with the identified driver nodes. We have integrated diverse network data and machine learning to predict repurposing of nine drugs for treatment of HL associated diseases.

Network analysis of synonymous codon usage

MOTIVATION

Most amino acids are encoded by multiple synonymous codons, some of which are used more rarely than others. Analyses of positions of such rare codons in protein sequences revealed that rare codons can impact co-translational protein folding and that positions of some rare codons are evolutionarily conserved. Analyses of their positions in protein 3-dimensional structures, which are richer in biochemical information than sequences alone, might further explain the role of rare codons in protein folding.

RESULTS

We model protein structures as networks and use network centrality to measure the structural position of an amino acid. We first validate that amino acids buried within the structural core are network-central, and those on the surface are not. Then, we study potential differences between network centralities and thus structural positions of amino acids encoded by conserved rare, non-conserved rare and commonly used codons. We find that in 84% of proteins, the three codon categories occupy significantly different structural positions. We examine protein groups showing different codon centrality trends, i.e. different relationships between structural positions of the three codon categories. We see several cases of all proteins from our data with some structural or functional property being in the same group. Also, we see a case of all proteins in some group having the same property. Our work shows that codon usage is linked to the final protein structure and thus possibly to co-translational protein folding.

AVAILABILITY AND IMPLEMENTATION

https://nd.edu/∼cone/CodonUsage/.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Complex Network Characterization Using Graph Theory and Fractal Geometry: The Case Study of Lung Cancer DNA Sequences

This paper discusses an approach developed for exploiting the local elementary movements of evolution to study complex networks in terms of shared common embedding and, consequently, shared fractal properties. This approach can be useful for the analysis of lung cancer DNA sequences and their properties by using the concepts of graph theory and fractal geometry. The proposed method advances a renewed consideration of network complexity both on local and global scales. Several researchers have illustrated the advantages of fractal mathematics, as well as its applicability to lung cancer research. Nevertheless, many researchers and clinicians continue to be unaware of its potential. Therefore, this paper aims to examine the underlying assumptions of fractals and analyze the fractal dimension and related measurements for possible application to complex networks and, especially, to the lung cancer network. The strict relationship between the lung cancer network properties and the fractal dimension is proved. Results show that the fractal dimension decreases in the lung cancer network while the topological properties of the network increase in the lung cancer network. Finally, statistical and topological significance between the complexity of the network and lung cancer network is shown.

The power of dynamic social networks to predict individuals' mental health

Precision medicine has received attention both in and outside the clinic. We focus on the latter, by exploiting the relationship between individuals' social interactions and their mental health to predict one's likelihood of being depressed or anxious from rich dynamic social network data. Existing studies differ from our work in at least one aspect: they do not model social interaction data as a network; they do so but analyze static network data; they examine "correlation" between social networks and health but without making any predictions; or they study other individual traits but not mental health. In a comprehensive evaluation, we show that our predictive model that uses dynamic social network data is superior to its static network as well as non-network equivalents when run on the same data. Supplementary material for this work is available at https://nd.edu/~cone/NetHealth/PSB_SM.pdf.

Network controllability analysis of intracellular signalling reveals viruses are actively controlling molecular systems

In recent years control theory has been applied to biological systems with the aim of identifying the minimum set of molecular interactions that can drive the network to a required state. However, in an intra-cellular network it is unclear how control can be achieved in practice. To address this limitation we use viral infection, specifically human immunodeficiency virus type 1 (HIV-1) and hepatitis C virus (HCV), as a paradigm to model control of an infected cell. Using a large human signalling network comprised of over 6000 human proteins and more than 34000 directed interactions, we compared two states: normal/uninfected and infected. Our network controllability analysis demonstrates how a virus efficiently brings the dynamically organised host system into its control by mostly targeting existing critical control nodes, requiring fewer nodes than in the uninfected network. The lower number of control nodes is presumably to optimise exploitation of specific sub-systems needed for virus replication and/or involved in the host response to infection. Viral infection of the human system also permits discrimination between available network-control models, which demonstrates that the minimum dominating set (MDS) method better accounts for how the biological information and signals are organised during infection by identifying most viral proteins as critical driver nodes compared to the maximum matching (MM) method. Furthermore, the host driver nodes identified by MDS are distributed throughout the pathways enabling effective control of the cell via the high ‘control centrality’ of the viral and targeted host nodes. Our results demonstrate that control theory gives a more complete and dynamic understanding of virus exploitation of the host system when compared with previous analyses limited to static single-state networks.

Finding and analysing the minimum set of driver nodes required to control multilayer networks

It is difficult to control multilayer networks in situations with real-world complexity. Here, we first define the multilayer control problem in terms of the minimum dominating set (MDS) controllability framework and mathematically demonstrate that simple formulas can be used to estimate the size of the minimum dominating set in multilayer (MDSM) complex networks. Second, we develop a new algorithm that efficiently identifies the MDSM in up to 6 layers, with several thousand nodes in each layer network. Interestingly, the findings reveal that the MDSM size for similar networks does not significantly differ from that required to control a single network. This result opens future directions for controlling, for example, multiple species by identifying a common set of enzymes or proteins for drug targeting. We apply our methods to 70 genome-wide metabolic networks across major plant lineages, unveiling some relationships between controllability in multilayer networks and metabolic functions at the genome scale.

An integrative network-based approach to identify novel disease genes and pathways: a case study in the context of inflammatory bowel disease

BACKGROUND

There are different and complicated associations between genes and diseases. Finding the causal associations between genes and specific diseases is still challenging. In this work we present a method to predict novel associations of genes and pathways with inflammatory bowel disease (IBD) by integrating information of differential gene expression, protein-protein interaction and known disease genes related to IBD.

RESULTS

We downloaded IBD gene expression data from NCBI's Gene Expression Omnibus, performed statistical analysis to determine differentially expressed genes, collected known IBD genes from DisGeNet database, which were used to construct a IBD related PPI network with HIPPIE database. We adapted our graph-based clustering algorithm DPClusO to cluster the disease PPI network. We evaluated the statistical significance of the identified clusters in the context of determining the richness of IBD genes using Fisher's exact test and predicted novel genes related to IBD. We showed 93.8% of our predictions are correct in the context of other databases and published literatures related to IBD.

CONCLUSIONS

Finding disease-causing genes is necessary for developing drugs with synergistic effect targeting many genes simultaneously. Here we present an approach to identify novel disease genes and pathways and discuss our approach in the context of IBD. The approach can be generalized to find disease-associated genes for other diseases.

Controllability in an islet specific regulatory network identifies the transcriptional factor NFATC4, which regulates Type 2 Diabetes associated genes

Probing the dynamic control features of biological networks represents a new frontier in capturing the dysregulated pathways in complex diseases. Here, using patient samples obtained from a pancreatic islet transplantation program, we constructed a tissue-specific gene regulatory network and used the control centrality (Cc) concept to identify the high control centrality (HiCc) pathways, which might serve as key pathobiological pathways for Type 2 Diabetes (T2D). We found that HiCc pathway genes were significantly enriched with modest GWAS p-values in the DIAbetes Genetics Replication And Meta-analysis (DIAGRAM) study. We identified variants regulating gene expression (expression quantitative loci, eQTL) of HiCc pathway genes in islet samples. These eQTL genes showed higher levels of differential expression compared to non-eQTL genes in low, medium, and high glucose concentrations in rat islets. Among genes with highly significant eQTL evidence, NFATC4 belonged to four HiCc pathways. We asked if the expressions of T2D-associated candidate genes from GWAS and literature are regulated by Nfatc4 in rat islets. Extensive in vitro silencing of Nfatc4 in rat islet cells displayed reduced expression of 16, and increased expression of four putative downstream T2D genes. Overall, our approach uncovers the mechanistic connection of NFATC4 with downstream targets including a previously unknown one, TCF7L2, and establishes the HiCc pathways' relationship to T2D.

The phenotype control kernel of a biomolecular regulatory network

Background

Controlling complex molecular regulatory networks is getting a growing attention as it can provide a systematic way of driving any cellular state to a desired cell phenotypic state. A number of recent studies suggested various control methods, but there is still deficiency in finding out practically useful control targets that ensure convergence of any initial network state to one of attractor states corresponding to a desired cell phenotype.

Results

To find out practically useful control targets, we introduce a new concept of phenotype control kernel (PCK) for a Boolean network, defined as the collection of all minimal sets of control nodes having their fixed state values that can generate all possible control sets which eventually drive any initial state to one of attractor states corresponding to a particular cell phenotype of interest. We also present a detailed method with which we can identify PCK in a systematic way based on the layered network and converging tree of a given network. We identify all candidates for control nodes from the layered network and then hierarchically search for all possible minimal sets by using the converging tree. We show the usefulness of PCK by applying it to cell proliferation and apoptosis signaling networks and comparing the results with other control methods. PCK is the unique control method for Boolean network models that can be used to identify all possible minimal sets of control nodes. Interestingly, many of the minimal sets have only one or two control nodes.

Conclusions

Based on the new concept of PCK, we can identify all possible minimal sets of control nodes that can drive any molecular network state to one of multiple attractor states representing a same desired cell phenotype.

Electronic supplementary material

The online version of this article (10.1186/s12918-018-0576-8) contains supplementary material, which is available to authorized users.

Network analysis of the NetHealth data: exploring co-evolution of individuals' social network positions and physical activities

Understanding the relationship between individuals' social networks and health could help devise public health interventions for reducing incidence of unhealthy behaviors or increasing prevalence of healthy ones. In this context, we explore the co-evolution of individuals' social network positions and physical activities. We are able to do so because the NetHealth study at the University of Notre Dame has generated both high-resolution longitudinal social network (e.g., SMS) data and high-resolution longitudinal health-related behavioral (e.g., Fitbit physical activity) data. We examine trait differences between (i) users whose social network positions (i.e., centralities) change over time versus those whose centralities remain stable, (ii) users whose Fitbit physical activities change over time versus those whose physical activities remain stable, and (iii) users whose centralities and their physical activities co-evolve, i.e., correlate with each other over time. We find that centralities of a majority of all nodes change with time. These users do not show any trait difference compared to time-stable users. However, if out of all users whose centralities change with time we focus on those whose physical activities also change with time, then the resulting users are more likely to be introverted than time-stable users. Moreover, users whose centralities and physical activities both change with time and whose evolving centralities are significantly correlated (i.e., co-evolve) with evolving physical activities are more likely to be introverted as well as anxious compared to those users who are time-stable and do not have a co-evolution relationship. Our network analysis framework reveals several links between individuals' social network structure, health-related behaviors, and the other (e.g., personality) traits. In the future, our study could lead to development of a predictive model of social network structure from behavioral/trait information and vice versa.

GRAFENE: Graphlet-based alignment-free network approach integrates 3D structural and sequence (residue order) data to improve protein structural comparison

Initial protein structural comparisons were sequence-based. Since amino acids that are distant in the sequence can be close in the 3-dimensional (3D) structure, 3D contact approaches can complement sequence approaches. Traditional 3D contact approaches study 3D structures directly and are alignment-based. Instead, 3D structures can be modeled as protein structure networks (PSNs). Then, network approaches can compare proteins by comparing their PSNs. These can be alignment-based or alignment-free. We focus on the latter. Existing network alignment-free approaches have drawbacks: 1) They rely on naive measures of network topology. 2) They are not robust to PSN size. They cannot integrate 3) multiple PSN measures or 4) PSN data with sequence data, although this could improve comparison because the different data types capture complementary aspects of the protein structure. We address this by: 1) exploiting well-established graphlet measures via a new network alignment-free approach, 2) introducing normalized graphlet measures to remove the bias of PSN size, 3) allowing for integrating multiple PSN measures, and 4) using ordered graphlets to combine the complementary PSN data and sequence (specifically, residue order) data. We compare synthetic networks and real-world PSNs more accurately and faster than existing network (alignment-free and alignment-based), 3D contact, or sequence approaches.

Critical controllability analysis of directed biological networks using efficient graph reduction

Network science has recently integrated key concepts from control theory and has applied them to the analysis of the controllability of complex networks. One of the proposed frameworks uses the Minimum Dominating Set (MDS) approach, which has been successfully applied to the identification of cancer-related proteins and in analyses of large-scale undirected networks, such as proteome-wide protein interaction networks. However, many real systems are better represented by directed networks. Therefore, fast algorithms are required for the application of MDS to directed networks. Here, we propose an algorithm that utilises efficient graph reduction to identify critical control nodes in large-scale directed complex networks. The algorithm is 176-fold faster than existing methods and increases the computable network size to 65,000 nodes. We then applied the developed algorithm to metabolic pathways consisting of 70 plant species encompassing major plant lineages ranging from algae to angiosperms and to signalling pathways from C. elegans, D. melanogaster and H. sapiens. The analysis not only identified functional pathways enriched with critical control molecules but also showed that most control categories are largely conserved across evolutionary time, from green algae and early basal plants to modern angiosperm plant lineages.

Improving Identification of Key Players in Aging via Network De-Noising and Core Inference

Current "ground truth" knowledge about human aging has been obtained by transferring aging-related knowledge from well-studied model species via sequence homology or by studying human gene expression data. Since proteins function by interacting with each other, analyzing protein-protein interaction (PPI) networks in the context of aging is promising. Unlike existing static network research of aging, since cellular functioning is dynamic, we recently integrated the static human PPI network with aging-related gene expression data to form dynamic, age-specific networks. Then, we predicted as key players in aging those proteins whose network topologies significantly changed with age. Since current networks are noisy , here, we use link prediction to de-noise the human network and predict improved key players in aging from the de-noised data. Indeed, de-noising gives more significant overlap between the predicted data and the "ground truth" aging-related data. Yet, we obtain novel predictions, which we validate in the literature. Also, we improve the predictions by an alternative strategy: removing "redundant" edges from the age-specific networks and using the resulting age-specific network "cores" to study aging. We produce new knowledge from dynamic networks encompassing multiple data types, via network de-noising or core inference, complementing the existing knowledge obtained from sequence or expression data.

Graph-theoretical model of global human interactome reveals enhanced long-range communicability in cancer networks

Malignant transformation is known to involve substantial rearrangement of the molecular genetic landscape of the cell. A common approach to analysis of these alterations is a reductionist one and consists of finding a compact set of differentially expressed genes or associated signaling pathways. However, due to intrinsic tumor heterogeneity and tissue specificity, biomarkers defined by a small number of genes/pathways exhibit substantial variability. As an alternative to compact differential signatures, global features of genetic cell machinery are conceivable. Global network descriptors suggested in previous works are, however, known to potentially be biased by overrepresentation of interactions between frequently studied genes-proteins. Here, we construct a cellular network of 74538 directional and differential gene expression weighted protein-protein and gene regulatory interactions, and perform graph-theoretical analysis of global human interactome using a novel, degree-independent feature—the normalized total communicability (NTC). We apply this framework to assess differences in total information flow between different cancer (BRCA/COAD/GBM) and non-cancer interactomes. Our experimental results reveal that different cancer interactomes are characterized by significant enhancement of long-range NTC, which arises from circulation of information flow within robustly organized gene subnetworks. Although enhancement of NTC emerges in different cancer types from different genomic profiles, we identified a subset of 90 common genes that are related to elevated NTC in all studied tumors. Our ontological analysis shows that these genes are associated with enhanced cell division, DNA replication, stress response, and other cellular functions and processes typically upregulated in cancer. We conclude that enhancement of long-range NTC manifested in the correlated activity of genes whose tight coordination is required for survival and proliferation of all tumor cells, and, thus, can be seen as a graph-theoretical equivalent to some hallmarks of cancer. The computational framework for differential network analysis presented herein is of potential interest for a wide range of network perturbation problems given by single or multiple gene-protein activation-inhibition.

A novel topological centrality measure capturing biologically important proteins

Topological centrality in protein interaction networks and its biological implications have widely been investigated in the past. In the present study, a novel metric of centrality-weighted sum of loads eigenvector centrality (WSL-EC)-based on graph spectra is defined and its performance in identifying topologically and biologically important nodes is comparatively investigated with common metrics of centrality in a human protein-protein interaction network. The metric can capture nodes from peripherals of the network differently from conventional eigenvector centrality. Different metrics were found to selectively identify hub sets that are significantly associated with different biological processes. The widely accepted metrics degree centrality, betweenness centrality, subgraph centrality and eigenvector centrality are subject to a bias towards super-hubs, whereas WSL-EC is not affected by the presence of super-hubs. WSL-EC outperforms other metrics of centrality in detecting biologically central nodes such as pathogen-interacting, cancer, ageing, HIV-1 or disease-related proteins and proteins involved in immune system processes and autoimmune diseases in the human interactome.

Observability transition in real networks

We consider the observability model in networks with arbitrary topologies. We introduce a system of coupled nonlinear equations, valid under the locally treelike ansatz, to describe the size of the largest observable cluster as a function of the fraction of directly observable nodes present in the network. We perform a systematic analysis on 95 real-world graphs and compare our theoretical predictions with numerical simulations of the observability model. Our method provides almost perfect predictions in the majority of the cases, even for networks with very large values of the clustering coefficient. Potential applications of our theory include the development of efficient and scalable algorithms for real-time surveillance of social networks, and monitoring of technological networks.

Comparative analysis of housekeeping and tissue-specific driver nodes in human protein interaction networks

Background

Several recent studies have used the Minimum Dominating Set (MDS) model to identify driver nodes, which provide the control of the underlying networks, in protein interaction networks. There may exist multiple MDS configurations in a given network, thus it is difficult to determine which one represents the real set of driver nodes. Because these previous studies only focus on static networks and ignore the contextual information on particular tissues, their findings could be insufficient or even be misleading.

Results

In this study, we develop a Collective-Influence-corrected Minimum Dominating Set (CI-MDS) model which takes into account the collective influence of proteins. By integrating molecular expression profiles and static protein interactions, 16 tissue-specific networks are established as well. We then apply the CI-MDS model to each tissue-specific network to detect MDS proteins. It generates almost the same MDSs when it is solved using different optimization algorithms. In addition, we classify MDS proteins into Tissue-Specific MDS (TS-MDS) proteins and HouseKeeping MDS (HK-MDS) proteins based on the number of tissues in which they are expressed and identified as MDS proteins. Notably, we find that TS-MDS proteins and HK-MDS proteins have significantly different topological and functional properties. HK-MDS proteins are more central in protein interaction networks, associated with more functions, evolving more slowly and subjected to a greater number of post-translational modifications than TS-MDS proteins. Unlike TS-MDS proteins, HK-MDS proteins significantly correspond to essential genes, ageing genes, virus-targeted proteins, transcription factors and protein kinases. Moreover, we find that besides HK-MDS proteins, many TS-MDS proteins are also linked to disease related genes, suggesting the tissue specificity of human diseases. Furthermore, functional enrichment analysis reveals that HK-MDS proteins carry out universally necessary biological processes and TS-MDS proteins usually involve in tissue-dependent functions.

Conclusions

Our study uncovers key features of TS-MDS proteins and HK-MDS proteins, and is a step forward towards a better understanding of the controllability of human interactomes.

Electronic supplementary material

The online version of this article (doi:10.1186/s12859-016-1233-0) contains supplementary material, which is available to authorized users.

Identification of key player genes in gene regulatory networks

Background

Identifying the gene regulatory networks governing the workings and identity of cells is one of the main challenges in understanding processes such as cellular differentiation, reprogramming or cancerogenesis. One particular challenge is to identify the main drivers and master regulatory genes that control such cell fate transitions. In this work, we reformulate this problem as the optimization problems of computing a Minimum Dominating Set and a Minimum Connected Dominating Set for directed graphs.

Results

Both MDS and MCDS are applied to the well-studied gene regulatory networks of the model organisms E. coli and S. cerevisiae and to a pluripotency network for mouse embryonic stem cells. The results show that MCDS can capture most of the known key player genes identified so far in the model organisms. Moreover, this method suggests an additional small set of transcription factors as novel key players for governing the cell-specific gene regulatory network which can also be investigated with regard to diseases. To this aim, we investigated the ability of MCDS to define key drivers in breast cancer. The method identified many known drug targets as members of the MDS and MCDS.

Conclusions

This paper proposes a new method to identify key player genes in gene regulatory networks. The Java implementation of the heuristic algorithm explained in this paper is available as a Cytoscape plugin at http://apps.cytoscape.org/apps/mcds. The SageMath programs for solving integer linear programming formulations used in the paper are available at https://github.com/maryamNazarieh/KeyRegulatoryGenesand as supplementary material.

Electronic supplementary material

The online version of this article (doi:10.1186/s12918-016-0329-5) contains supplementary material, which is available to authorized users.

Genome-wide profiling of 24 hr diel rhythmicity in the water flea, Daphnia pulex: network analysis reveals rhythmic gene expression and enhances functional gene annotation

Background

Marine and freshwater zooplankton exhibit daily rhythmic patterns of behavior and physiology which may be regulated directly by the light:dark (LD) cycle and/or a molecular circadian clock. One of the best-studied zooplankton taxa, the freshwater crustacean Daphnia, has a 24 h diel vertical migration (DVM) behavior whereby the organism travels up and down through the water column daily. DVM plays a critical role in resource tracking and the behavioral avoidance of predators and damaging ultraviolet radiation. However, there is little information at the transcriptional level linking the expression patterns of genes to the rhythmic physiology/behavior of Daphnia.

Results

Here we analyzed genome-wide temporal transcriptional patterns from Daphnia pulex collected over a 44 h time period under a 12:12 LD cycle (diel) conditions using a cosine-fitting algorithm. We used a comprehensive network modeling and analysis approach to identify novel co-regulated rhythmic genes that have similar network topological properties and functional annotations as rhythmic genes identified by the cosine-fitting analyses. Furthermore, we used the network approach to predict with high accuracy novel gene-function associations, thus enhancing current functional annotations available for genes in this ecologically relevant model species. Our results reveal that genes in many functional groupings exhibit 24 h rhythms in their expression patterns under diel conditions. We highlight the rhythmic expression of immunity, oxidative detoxification, and sensory process genes. We discuss differences in the chronobiology of D. pulex from other well-characterized terrestrial arthropods.

Conclusions

This research adds to a growing body of literature suggesting the genetic mechanisms governing rhythmicity in crustaceans may be divergent from other arthropod lineages including insects. Lastly, these results highlight the power of using a network analysis approach to identify differential gene expression and provide novel functional annotation.

Electronic supplementary material

The online version of this article (doi:10.1186/s12864-016-2998-2) contains supplementary material, which is available to authorized users.

Analysis of the Effect of Degree Correlation on the Size of Minimum Dominating Sets in Complex Networks

Network controllability is an important topic in wide-ranging research fields. However, the relationship between controllability and network structure is poorly understood, although degree heterogeneity is known to determine the controllability. We focus on the size of a minimum dominating set (MDS), a measure of network controllability, and investigate the effect of degree-degree correlation, which is universally observed in real-world networks, on the size of an MDS. We show that disassortativity or negative degree-degree correlation reduces the size of an MDS using analytical treatments and numerical simulation, whereas positive correlations hardly affect the size of an MDS. This result suggests that disassortativity enhances network controllability. Furthermore, apart from the controllability issue, the developed techniques provide new ways of analyzing complex networks with degree-degree correlations.

Boolean modeling techniques for protein co-expression networks in systems medicine

INTRODUCTION

Application of systems biology/systems medicine approaches is promising for proteomics/biomedical research, but requires selection of an adequate modeling type.

AREAS COVERED

This article reviews the existing Boolean network modeling approaches, which provide in comparison with alternative modeling techniques several advantages for the processing of proteomics data. Application of methods for inference, reduction and validation of protein co-expression networks that are derived from quantitative high-throughput proteomics measurements is presented. It's also shown how Boolean models can be used to derive system-theoretic characteristics that describe both the dynamical behavior of such networks as a whole and the properties of different cell states (e.g. healthy or diseased cell states). Furthermore, application of methods derived from control theory is proposed in order to simulate the effects of therapeutic interventions on such networks, which is a promising approach for the computer-assisted discovery of biomarkers and drug targets. Finally, the clinical application of Boolean modeling analyses is discussed. Expert commentary: Boolean modeling of proteomics data is still in its infancy. Progress in this field strongly depends on provision of a repository with public access to relevant reference models. Also required are community supported standards that facilitate input of both proteomics and patient related data (e.g. age, gender, laboratory results, etc.).

Critical controllability in proteome-wide protein interaction network integrating transcriptome

Recently, the number of essential gene entries has considerably increased. However, little is known about the relationships between essential genes and their functional roles in critical network control at both the structural (protein interaction network) and dynamic (transcriptional) levels, in part because the large size of the network prevents extensive computational analysis. Here, we present an algorithm that identifies the critical control set of nodes by reducing the computational time by 180 times and by expanding the computable network size up to 25 times, from 1,000 to 25,000 nodes. The developed algorithm allows a critical controllability analysis of large integrated systems composed of a transcriptome- and proteome-wide protein interaction network for the first time. The data-driven analysis captures a direct triad association of the structural controllability of genes, lethality and dynamic synchronization of co-expression. We believe that the identified optimized critical network control subsets may be of interest as drug targets; thus, they may be useful for drug design and development.

Minimum dominating set-based methods for analyzing biological networks

The fast increase of 'multi-omics' data does not only pose a computational challenge for its analysis but also requires novel algorithmic methodologies to identify complex biological patterns and decipher the ultimate roots of human disorders. To that end, the massive integration of omics data with disease phenotypes is offering a new window into the cell functionality. The minimum dominating set (MDS) approach has rapidly emerged as a promising algorithmic method to analyze complex biological networks integrated with human disorders, which can be composed of a variety of omics data, from proteomics and transcriptomics to metabolomics. Here we review the main theoretical foundations of the methodology and the key algorithms, and examine the recent applications in which biological systems are analyzed by using the MDS approach.

Determining Associations between Human Diseases and non-coding RNAs with Critical Roles in Network Control

Deciphering the association between life molecules and human diseases is currently an important task in systems biology. Research over the past decade has unveiled that the human genome is almost entirely transcribed, producing a vast number of non-protein-coding RNAs (ncRNAs) with potential regulatory functions. More recent findings suggest that many diseases may not be exclusively linked to mutations in protein-coding genes. The combination of these arguments poses the question of whether ncRNAs that play a critical role in network control are also enriched with disease-associated ncRNAs. To address this question, we mapped the available annotated information of more than 350 human disorders to the largest collection of human ncRNA-protein interactions, which define a bipartite network of almost 93,000 interactions. Using a novel algorithmic-based controllability framework applied to the constructed bipartite network, we found that ncRNAs engaged in critical network control are also statistically linked to human disorders (P-value of P = 9.8 × 10⁻¹⁰⁹). Taken together, these findings suggest that the addition of those genes that encode optimized subsets of ncRNAs engaged in critical control within the pool of candidate genes could aid disease gene prioritization studies.

Novel drug target identification for the treatment of dementia using multi-relational association mining

Dementia is a neurodegenerative condition of the brain in which there is a progressive and permanent loss of cognitive and mental performance. Despite the fact that the number of people with dementia worldwide is steadily increasing and regardless of the advances in the molecular characterization of the disease, current medical treatments for dementia are purely symptomatic and hardly effective. We present a novel multi-relational association mining method that integrates the huge amount of scientific data accumulated in recent years to predict potential novel targets for innovative therapeutic treatment of dementia. Owing to the ability of processing large volumes of heterogeneous data, our method achieves a high performance and predicts numerous drug targets including several serine threonine kinase and a G-protein coupled receptor. The predicted drug targets are mainly functionally related to metabolism, cell surface receptor signaling pathways, immune response, apoptosis, and long-term memory. Among the highly represented kinase family and among the G-protein coupled receptors, DLG4 (PSD-95), and the bradikynin receptor 2 are highlighted also for their proposed role in memory and cognition, as described in previous studies. These novel putative targets hold promises for the development of novel therapeutic approaches for the treatment of dementia.

Exploring the structure and function of temporal networks with dynamic graphlets

MOTIVATION

With increasing availability of temporal real-world networks, how to efficiently study these data? One can model a temporal network as a single aggregate static network, or as a series of time-specific snapshots, each being an aggregate static network over the corresponding time window. Then, one can use established methods for static analysis on the resulting aggregate network(s), but losing in the process valuable temporal information either completely, or at the interface between different snapshots, respectively. Here, we develop a novel approach for studying a temporal network more explicitly, by capturing inter-snapshot relationships.

RESULTS

We base our methodology on well-established graphlets (subgraphs), which have been proven in numerous contexts in static network research. We develop new theory to allow for graphlet-based analyses of temporal networks. Our new notion of dynamic graphlets is different from existing dynamic network approaches that are based on temporal motifs (statistically significant subgraphs). The latter have limitations: their results depend on the choice of a null network model that is required to evaluate the significance of a subgraph, and choosing a good null model is non-trivial. Our dynamic graphlets overcome the limitations of the temporal motifs. Also, when we aim to characterize the structure and function of an entire temporal network or of individual nodes, our dynamic graphlets outperform the static graphlets. Clearly, accounting for temporal information helps. We apply dynamic graphlets to temporal age-specific molecular network data to deepen our limited knowledge about human aging.

AVAILABILITY AND IMPLEMENTATION

http://www.nd.edu/∼cone/DG.

Fair evaluation of global network aligners

BACKGROUND

Analogous to genomic sequence alignment, biological network alignment identifies conserved regions between networks of different species. Then, function can be transferred from well- to poorly-annotated species between aligned network regions. Network alignment typically encompasses two algorithmic components: node cost function (NCF), which measures similarities between nodes in different networks, and alignment strategy (AS), which uses these similarities to rapidly identify high-scoring alignments. Different methods use both different NCFs and different ASs. Thus, it is unclear whether the superiority of a method comes from its NCF, its AS, or both. We already showed on state-of-the-art methods, MI-GRAAL and IsoRankN, that combining NCF of one method and AS of another method can give a new superior method. Here, we evaluate MI-GRAAL against a newer approach, GHOST, by mixing-and-matching the methods' NCFs and ASs to potentially further improve alignment quality. While doing so, we approach important questions that have not been asked systematically thus far. First, we ask how much of the NCF information should come from protein sequence data compared to network topology data. Existing methods determine this parameter more-less arbitrarily, which could affect alignment quality. Second, when topological information is used in NCF, we ask how large the size of the neighborhoods of the compared nodes should be. Existing methods assume that the larger the neighborhood size, the better.

RESULTS

Our findings are as follows. MI-GRAAL's NCF is superior to GHOST's NCF, while the performance of the methods' ASs is data-dependent. Thus, for data on which GHOST's AS is superior to MI-GRAAL's AS, the combination of MI-GRAAL's NCF and GHOST's AS represents a new superior method. Also, which amount of sequence information is used within NCF does not affect alignment quality, while the inclusion of topological information is crucial for producing good alignments. Finally, larger neighborhood sizes are preferred, but often, it is the second largest size that is superior. Using this size instead of the largest one would decrease computational complexity.

CONCLUSION

Taken together, our results represent general recommendations for a fair evaluation of network alignment methods and in particular of two-stage NCF-AS approaches.

Determining minimum set of driver nodes in protein-protein interaction networks

BACKGROUND

Recently, several studies have drawn attention to the determination of a minimum set of driver proteins that are important for the control of the underlying protein-protein interaction (PPI) networks. In general, the minimum dominating set (MDS) model is widely adopted. However, because the MDS model does not generate a unique MDS configuration, multiple different MDSs would be generated when using different optimization algorithms. Therefore, among these MDSs, it is difficult to find out the one that represents the true driver set of proteins.

RESULTS

To address this problem, we develop a centrality-corrected minimum dominating set (CC-MDS) model which includes heterogeneity in degree and betweenness centralities of proteins. Both the MDS model and the CC-MDS model are applied on three human PPI networks. Unlike the MDS model, the CC-MDS model generates almost the same sets of driver proteins when we implement it using different optimization algorithms. The CC-MDS model targets more high-degree and high-betweenness proteins than the uncorrected counterpart. The more central position allows CC-MDS proteins to be more important in maintaining the overall network connectivity than MDS proteins. To indicate the functional significance, we find that CC-MDS proteins are involved in, on average, more protein complexes and GO annotations than MDS proteins. We also find that more essential genes, aging genes, disease-associated genes and virus-targeted genes appear in CC-MDS proteins than in MDS proteins. As for the involvement in regulatory functions, the sets of CC-MDS proteins show much stronger enrichment of transcription factors and protein kinases. The results about topological and functional significance demonstrate that the CC-MDS model can capture more driver proteins than the MDS model.

CONCLUSIONS

Based on the results obtained, the CC-MDS model presents to be a powerful tool for the determination of driver proteins that can control the underlying PPI networks. The software described in this paper and the datasets used are available at https://github.com/Zhangxf-ccnu/CC-MDS .

Essentiality and centrality in protein interaction networks revisited

Background

Minimum dominating sets (MDSet) of protein interaction networks allow the control of underlying protein interaction networks through their topological placement. While essential proteins are enriched in MDSets, we hypothesize that the statistical properties of biological functions of essential genes are enhanced when we focus on essential MDSet proteins (e-MDSet).

Results

Here, we determined minimum dominating sets of proteins (MDSet) in interaction networks of E. coli, S. cerevisiae and H. sapiens, defined as subsets of proteins whereby each remaining protein can be reached by a single interaction. We compared several topological and functional parameters of essential, MDSet, and essential MDSet (e-MDSet) proteins. In particular, we observed that their topological placement allowed e-MDSet proteins to provide a positive correlation between degree and lethality, connect more protein complexes, and have a stronger impact on network resilience than essential proteins alone. In comparison to essential proteins we further found that interactions between e-MDSet proteins appeared more frequently within complexes, while interactions of e-MDSet proteins between complexes were depleted. Finally, these e-MDSet proteins classified into functional groupings that play a central role in survival and adaptability.

Conclusions

The determination of e-MDSet of an organism highlights a set of proteins that enhances the enrichment signals of biological functions of essential proteins. As a consequence, we surmise that e-MDSets may provide a new method of evaluating the core proteins of an organism.

Global Network Alignment in the Context of Aging

Analogous to sequence alignment, network alignment (NA) can be used to transfer biological knowledge across species between conserved network regions. NA faces two algorithmic challenges: 1) Which cost function to use to capture "similarities" between nodes in different networks? 2) Which alignment strategy to use to rapidly identify "high-scoring" alignments from all possible alignments? We "break down" existing state-of-the-art methods that use both different cost functions and different alignment strategies to evaluate each combination of their cost functions and alignment strategies. We find that a combination of the cost function of one method and the alignment strategy of another method beats the existing methods. Hence, we propose this combination as a novel superior NA method. Then, since human aging is hard to study experimentally due to long lifespan, we use NA to transfer aging-related knowledge from well annotated model species to poorly annotated human. By doing so, we produce novel human aging-related knowledge, which complements currently available knowledge about aging that has been obtained mainly by sequence alignment. We demonstrate significant similarity between topological and functional properties of our novel predictions and those of known aging-related genes. We are the first to use NA to learn more about aging.

Predicting disease associations via biological network analysis

Background

Understanding the relationship between diseases based on the underlying biological mechanisms is one of the greatest challenges in modern biology and medicine. Exploring disease-disease associations by using system-level biological data is expected to improve our current knowledge of disease relationships, which may lead to further improvements in disease diagnosis, prognosis and treatment.

Results

We took advantage of diverse biological data including disease-gene associations and a large-scale molecular network to gain novel insights into disease relationships. We analysed and compared four publicly available disease-gene association datasets, then applied three disease similarity measures, namely annotation-based measure, function-based measure and topology-based measure, to estimate the similarity scores between diseases. We systematically evaluated disease associations obtained by these measures against a statistical measure of comorbidity which was derived from a large number of medical patient records. Our results show that the correlation between our similarity measures and comorbidity scores is substantially higher than expected at random, confirming that our similarity measures are able to recover comorbidity associations. We also demonstrated that our predicted disease associations correlated with disease associations generated from genome-wide association studies significantly higher than expected at random. Furthermore, we evaluated our predicted disease associations via mining the literature on PubMed, and presented case studies to demonstrate how these novel disease associations can be used to enhance our current knowledge of disease relationships.

Conclusions

We present three similarity measures for predicting disease associations. The strong correlation between our predictions and known disease associations demonstrates the ability of our measures to provide novel insights into disease relationships.

Electronic supplementary material

The online version of this article (doi:10.1186/1471-2105-15-304) contains supplementary material, which is available to authorized users.

Networks' Characteristics Matter for Systems Biology

A fundamental goal of systems biology is to create models that describe relationships between biological components. Networks are an increasingly popular approach to this problem. However, a scientist interested in modeling biological (e.g., gene expression) data as a network is quickly confounded by the fundamental problem: how to construct the network? It is fairly easy to construct a network, but is it the network for the problem being considered? This is an important problem with three fundamental issues: How to weight edges in the network in order to capture actual biological interactions? What is the effect of the type of biological experiment used to collect the data from which the network is constructed? How to prune the weighted edges (or what cut-off to apply)? Differences in the construction of networks could lead to different biological interpretations. Indeed, we find that there are statistically significant dissimilarities in the functional content and topology between gene co-expression networks constructed using different edge weighting methods, data types, and edge cut-offs. We show that different types of known interactions, such as those found through Affinity Capture-Luminescence or Synthetic Lethality experiments, appear in significantly varying amounts in networks constructed in different ways. Hence, we demonstrate that different biological questions may be answered by the different networks. Consequently, we posit that the approach taken to build a network can be matched to biological questions to get targeted answers. More study is required to understand the implications of different network inference approaches and to draw reliable conclusions from networks used in the field of systems biology.

Targeting molecular networks for drug research

The study of molecular networks has recently moved into the limelight of biomedical research. While it has certainly provided us with plenty of new insights into cellular mechanisms, the challenge now is how to modify or even restructure these networks. This is especially true for human diseases, which can be regarded as manifestations of distorted states of molecular networks. Of the possible interventions for altering networks, the use of drugs is presently the most feasible. In this mini-review, we present and discuss some exemplary approaches of how analysis of molecular interaction networks can contribute to pharmacology (e.g., by identifying new drug targets or prediction of drug side effects), as well as list pointers to relevant resources and software to guide future research. We also outline recent progress in the use of drugs for in vitro reprogramming of cells, which constitutes an example par excellence for altering molecular interaction networks with drugs.

Revealing missing parts of the interactome via link prediction

Protein interaction networks (PINs) are often used to "learn" new biological function from their topology. Since current PINs are noisy, their computational de-noising via link prediction (LP) could improve the learning accuracy. LP uses the existing PIN topology to predict missing and spurious links. Many of existing LP methods rely on shared immediate neighborhoods of the nodes to be linked. As such, they have limitations. Thus, in order to comprehensively study what are the topological properties of nodes in PINs that dictate whether the nodes should be linked, we introduce novel sensitive LP measures that are expected to overcome the limitations of the existing methods. We systematically evaluate the new and existing LP measures by introducing "synthetic" noise into PINs and measuring how accurate the measures are in reconstructing the original PINs. Also, we use the LP measures to de-noise the original PINs, and we measure biological correctness of the de-noised PINs with respect to functional enrichment of the predicted interactions. Our main findings are: 1) LP measures that favor nodes which are both "topologically similar" and have large shared extended neighborhoods are superior; 2) using more network topology often though not always improves LP accuracy; and 3) LP improves biological correctness of the PINs, plus we validate a significant portion of the predicted interactions in independent, external PIN data sources. Ultimately, we are less focused on identifying a superior method but more on showing that LP improves biological correctness of PINs, which is its ultimate goal in computational biology. But we note that our new methods outperform each of the existing ones with respect to at least one evaluation criterion. Alarmingly, we find that the different criteria often disagree in identifying the best method(s), which has important implications for LP communities in any domain, including social networks.

Dynamic networks reveal key players in aging

MOTIVATION

Because susceptibility to diseases increases with age, studying aging gains importance. Analyses of gene expression or sequence data, which have been indispensable for investigating aging, have been limited to studying genes and their protein products in isolation, ignoring their connectivities. However, proteins function by interacting with other proteins, and this is exactly what biological networks (BNs) model. Thus, analyzing the proteins' BN topologies could contribute to the understanding of aging. Current methods for analyzing systems-level BNs deal with their static representations, even though cells are dynamic. For this reason, and because different data types can give complementary biological insights, we integrate current static BNs with aging-related gene expression data to construct dynamic age-specific BNs. Then, we apply sensitive measures of topology to the dynamic BNs to study cellular changes with age.

RESULTS

While global BN topologies do not significantly change with age, local topologies of a number of genes do. We predict such genes to be aging-related. We demonstrate credibility of our predictions by (i) observing significant overlap between our predicted aging-related genes and 'ground truth' aging-related genes; (ii) observing significant overlap between functions and diseases that are enriched in our aging-related predictions and those that are enriched in 'ground truth' aging-related data; (iii) providing evidence that diseases which are enriched in our aging-related predictions are linked to human aging; and (iv) validating our high-scoring novel predictions in the literature.

AVAILABILITY AND IMPLEMENTATION

Software executables are available upon request.

Systems biology approach to stage-wise characterization of epigenetic genes in lung adenocarcinoma

Background

Epigenetics refers to the reversible functional modifications of the genome that do not correlate to changes in the DNA sequence. The aim of this study is to understand DNA methylation patterns across different stages of lung adenocarcinoma (LUAD).

Results

Our study identified 72, 93 and 170 significant DNA methylated genes in Stages I, II and III respectively. A set of common 34 significant DNA methylated genes located in the promoter section of the true CpG islands were found across stages, and these were: HOX genes, FOXG1, GRIK3, HAND2, PRKCB, etc. Of the total significant DNA methylated genes, 65 correlated with transcription function. The epigenetic analysis identified the following novel genes across all stages: PTGDR, TLX3, and POU4F2. The stage-wise analysis observed the appearance of NEUROG1 gene in Stage I and its re-appearance in Stage III. The analysis showed similar epigenetic pattern across Stage I and Stage III. Pathway analysis revealed important signaling and metabolic pathways of LUAD to correlate with epigenetics. Epigenetic subnetwork analysis identified a set of seven conserved genes across all stages: UBC, KRAS, PIK3CA, PIK3R3, RAF1, BRAF, and RAP1A. A detailed literature analysis elucidated epigenetic genes like FOXG1, HLA-G, and NKX6-2 to be known as prognostic targets.

Conclusion

Integrating epigenetic information for genes with expression data can be useful for comprehending in-depth disease mechanism and for the ultimate goal of better target identification.

A combinatorial approach to graphlet counting

MOTIVATION

Small-induced subgraphs called graphlets are emerging as a possible tool for exploration of global and local structure of networks and for analysis of roles of individual nodes. One of the obstacles to their wider use is the computational complexity of algorithms for their discovery and counting.

RESULTS

We propose a new combinatorial method for counting graphlets and orbit signatures of network nodes. The algorithm builds a system of equations that connect counts of orbits from graphlets with up to five nodes, which allows to compute all orbit counts by enumerating just a single one. This reduces its practical time complexity in sparse graphs by an order of magnitude as compared with the existing pure enumeration-based algorithms.

AVAILABILITY AND IMPLEMENTATION

Source code is available freely at http://www.biolab.si/supp/orca/orca.html.

Sharp bounds and normalization of Wiener-type indices

Complex networks abound in physical, biological and social sciences. Quantifying a network’s topological structure facilitates network exploration and analysis, and network comparison, clustering and classification. A number of Wiener type indices have recently been incorporated as distance-based descriptors of complex networks, such as the R package QuACN. Wiener type indices are known to depend both on the network’s number of nodes and topology. To apply these indices to measure similarity of networks of different numbers of nodes, normalization of these indices is needed to correct the effect of the number of nodes in a network. This paper aims to fill this gap. Moreover, we introduce an -Wiener index of network , denoted by . This notion generalizes the Wiener index to a very wide class of Wiener type indices including all known Wiener type indices. We identify the maximum and minimum of over a set of networks with nodes. We then introduce our normalized-version of -Wiener index. The normalized -Wiener indices were demonstrated, in a number of experiments, to improve significantly the hierarchical clustering over the non-normalized counterparts.

An extended network of genomic maintenance in the archaeon Pyrococcus abyssi highlights unexpected associations between eucaryotic homologs

In Archaea, the proteins involved in the genetic information processing pathways, including DNA replication, transcription, and translation, share strong similarities with those of eukaryotes. Characterizations of components of the eukaryotic-type replication machinery complex provided many interesting insights into DNA replication in both domains. In contrast, DNA repair processes of hyperthermophilic archaea are less well understood and very little is known about the intertwining between DNA synthesis, repair and recombination pathways. The development of genetic system in hyperthermophilic archaea is still at a modest stage hampering the use of complementary approaches of reverse genetics and biochemistry to elucidate the function of new candidate DNA repair gene. To gain insights into genomic maintenance processes in hyperthermophilic archaea, a protein-interaction network centred on informational processes of Pyrococcus abyssi was generated by affinity purification coupled with mass spectrometry. The network consists of 132 interactions linking 87 proteins. These interactions give insights into the connections of DNA replication with recombination and repair, leading to the discovery of new archaeal components and of associations between eucaryotic homologs. Although this approach did not allow us to clearly delineate new DNA pathways, it provided numerous clues towards the function of new molecular complexes with the potential to better understand genomic maintenance processes in hyperthermophilic archaea. Among others, we found new potential partners of the replication clamp and demonstrated that the single strand DNA binding protein, Replication Protein A, enhances the transcription rate, in vitro, of RNA polymerase. This interaction map provides a valuable tool to explore new aspects of genome integrity in Archaea and also potentially in Eucaryotes.

Structure and dynamics of molecular networks: a novel paradigm of drug discovery: a comprehensive review

Despite considerable progress in genome- and proteome-based high-throughput screening methods and in rational drug design, the increase in approved drugs in the past decade did not match the increase of drug development costs. Network description and analysis not only give a systems-level understanding of drug action and disease complexity, but can also help to improve the efficiency of drug design. We give a comprehensive assessment of the analytical tools of network topology and dynamics. The state-of-the-art use of chemical similarity, protein structure, protein-protein interaction, signaling, genetic interaction and metabolic networks in the discovery of drug targets is summarized. We propose that network targeting follows two basic strategies. The "central hit strategy" selectively targets central nodes/edges of the flexible networks of infectious agents or cancer cells to kill them. The "network influence strategy" works against other diseases, where an efficient reconfiguration of rigid networks needs to be achieved by targeting the neighbors of central nodes/edges. It is shown how network techniques can help in the identification of single-target, edgetic, multi-target and allo-network drug target candidates. We review the recent boom in network methods helping hit identification, lead selection optimizing drug efficacy, as well as minimizing side-effects and drug toxicity. Successful network-based drug development strategies are shown through the examples of infections, cancer, metabolic diseases, neurodegenerative diseases and aging. Summarizing >1200 references we suggest an optimized protocol of network-aided drug development, and provide a list of systems-level hallmarks of drug quality. Finally, we highlight network-related drug development trends helping to achieve these hallmarks by a cohesive, global approach.

Biological function through network topology: a survey of the human diseasome

Molecular network data are increasingly becoming available, necessitating the development of well performing computational tools for their analyses. Such tools enabled conceptually different approaches for exploring human diseases to be undertaken, in particular, those that study the relationship between a multitude of biomolecules within a cell. Hence, a new field of network biology has emerged as part of systems biology, aiming to untangle the complexity of cellular network organization. We survey current network analysis methods that aim to give insight into human disease.

Graphlet-based edge clustering reveals pathogen-interacting proteins

MOTIVATION

Prediction of protein function from protein interaction networks has received attention in the post-genomic era. A popular strategy has been to cluster the network into functionally coherent groups of proteins and assign the entire cluster with a function based on functions of its annotated members. Traditionally, network research has focused on clustering of nodes. However, clustering of edges may be preferred: nodes belong to multiple functional groups, but clustering of nodes typically cannot capture the group overlap, while clustering of edges can. Clustering of adjacent edges that share many neighbors was proposed recently, outperforming different node clustering methods. However, since some biological processes can have characteristic 'signatures' throughout the network, not just locally, it may be of interest to consider edges that are not necessarily adjacent.

RESULTS

We design a sensitive measure of the 'topological similarity' of edges that can deal with edges that are not necessarily adjacent. We cluster edges that are similar according to our measure in different baker's yeast protein interaction networks, outperforming existing node and edge clustering approaches. We apply our approach to the human network to predict new pathogen-interacting proteins. This is important, since these proteins represent drug target candidates.

AVAILABILITY

Software executables are freely available upon request.

CONTACT

tmilenko@nd.edu

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.