Clustering complex networks and biological networks by nonnegative matrix factorization with various similarity measures

Overview of methods for characterization and visualization of a protein-protein interaction network in a multi-omics integration context

At the heart of the cellular machinery through the regulation of cellular functions, protein-protein interactions (PPIs) have a significant role. PPIs can be analyzed with network approaches. Construction of a PPI network requires prediction of the interactions. All PPIs form a network. Different biases such as lack of data, recurrence of information, and false interactions make the network unstable. Integrated strategies allow solving these different challenges. These approaches have shown encouraging results for the understanding of molecular mechanisms, drug action mechanisms, and identification of target genes. In order to give more importance to an interaction, it is evaluated by different confidence scores. These scores allow the filtration of the network and thus facilitate the representation of the network, essential steps to the identification and understanding of molecular mechanisms. In this review, we will discuss the main computational methods for predicting PPI, including ones confirming an interaction as well as the integration of PPIs into a network, and we will discuss visualization of these complex data.

Multi-Objective Evolutionary Algorithms to Find Community Structures in Large Networks

Real-world complex systems are often modeled by networks such that the elements are represented by vertices and their interactions are represented by edges. An important characteristic of these networks is that they contain clusters of vertices densely linked amongst themselves and more sparsely connected to nodes outside the cluster. Community detection in networks has become an emerging area of investigation in recent years, but most papers aim to solve single-objective formulations, often focused on optimizing structural metrics, including the modularity measure. However, several studies have highlighted that considering modularityas a unique objective often involves resolution limit and imbalance inconveniences. This paper opens a new avenue of research in the study of multi-objective variants of the classical community detection problem by applying multi-objective evolutionary algorithms that simultaneously optimize different objectives. In particular, they analyzed two multi-objective variants involving not only modularity but also the conductance metric and the imbalance in the number of nodes of the communities. With this aim, a new Pareto-based multi-objective evolutionary algorithm is presented that includes advanced initialization strategies and search operators. The results obtained when solving large-scale networks representing real-life power systems show the good performance of these methods and demonstrate that it is possible to obtain a balanced number of nodes in the clusters formed while also having high modularity and conductance values.

Time course regulatory analysis based on paired expression and chromatin accessibility data

A time course experiment is a widely used design in the study of cellular processes such as differentiation or response to stimuli. In this paper, we propose time course regulatory analysis (TimeReg) as a method for the analysis of gene regulatory networks based on paired gene expression and chromatin accessibility data from a time course. TimeReg can be used to prioritize regulatory elements, to extract core regulatory modules at each time point, to identify key regulators driving changes of the cellular state, and to causally connect the modules across different time points. We applied the method to analyze paired chromatin accessibility and gene expression data from a retinoic acid (RA)-induced mouse embryonic stem cells (mESCs) differentiation experiment. The analysis identified 57,048 novel regulatory elements regulating cerebellar development, synapse assembly, and hindbrain morphogenesis, which substantially extended our knowledge of cis-regulatory elements during differentiation. Using single-cell RNA-seq data, we showed that the core regulatory modules can reflect the properties of different subpopulations of cells. Finally, the driver regulators are shown to be important in clarifying the relations between modules across adjacent time points. As a second example, our method on Ascl1-induced direct reprogramming from fibroblast to neuron time course data identified Id1/2 as driver regulators of early stage of reprogramming.

A network clustering based feature selection strategy for classifying autism spectrum disorder

BACKGROUND

Advanced non-invasive neuroimaging techniques offer new approaches to study functions and structures of human brains. Whole-brain functional networks obtained from resting state functional magnetic resonance imaging has been widely used to study brain diseases like autism spectrum disorder (ASD). Auto-classification of ASD has become an important issue. Existing classification methods for ASD are based on features extracted from the whole-brain functional networks, which may be not discriminant enough for good performance.

METHODS

In this study, we propose a network clustering based feature selection strategy for classifying ASD. In our proposed method, we first apply symmetric non-negative matrix factorization to divide brain networks into four modules. Then we extract features from one of four modules called default mode network (DMN) and use them to train several classifiers for ASD classification.

RESULTS

The computational experiments show that our proposed method achieves better performances than those trained with features extracted from the whole brain network.

CONCLUSION

It is a good strategy to train the classifiers for ASD based on features from the default mode subnetwork.

Comparing methods of grouping hospitals

OBJECTIVE

To compare the performance of widely used approaches for defining groups of hospitals and a new approach based on network analysis of shared patient volume.

STUDY SETTING

Non-federal acute care hospitals in the United States.

STUDY DESIGN

We assessed the measurement properties of four methods of grouping hospitals: hospital referral regions (HRRs), metropolitan statistical areas (MSAs), core-based statistical areas (CBSAs), and community detection algorithms (CDAs).

DATA EXTRACTION METHODS

We combined data from the 2014 American Hospital Association Annual Survey, the Census Bureau, the Dartmouth Atlas, and Medicare data on interhospital patient travel patterns. We then evaluated the distinctiveness of each grouping, reliability over time, and generalizability across populations.

PRINCIPLE FINDINGS

Hospital groups defined by CDAs were the most distinctive (modularity = 0.86 compared to 0.75 for HRRs and 0.83 for MSAs; 0.72 for CBSA), were reliable to alternative specifications, and had greater generalizability than HRRs, MSAs, or CBSAs. CDAs had lower reliability over time than MSAs or CBSAs (normalized mutual information between 2012 and 2014 CDAs = 0.93).

CONCLUSIONS

Community detection algorithm-defined hospital groups offer high validity, reliability to different specifications, and generalizability to many uses when compared to approaches in widespread use today. They may, therefore, offer a better choice for efforts seeking to analyze the behaviors and dynamics of groups of hospitals. Measures of modularity, shared information, inclusivity, and shared behavior can be used to evaluate different approaches to grouping providers.

Overlapping functional modules detection in PPI network with pair-wise constrained non-negative matrix tri-factorisation

A large amount of available protein–protein interaction (PPI) data has been generated by high‐throughput experimental techniques. Uncovering functional modules from PPI networks will help us better understand the underlying mechanisms of cellular functions. Numerous computational algorithms have been designed to identify functional modules automatically in the past decades. However, most community detection methods (non‐overlapping or overlapping types) are unsupervised models, which cannot incorporate the well‐known protein complexes as a priori. The authors propose a novel semi‐supervised model named pairwise constrains nonnegative matrix tri‐factorisation (PCNMTF), which takes full advantage of the well‐known protein complexes to find overlapping functional modules based on protein module indicator matrix and module correlation matrix simultaneously from PPI networks. PCNMTF determinately models and learns the mixed module memberships of each protein by considering the correlation among modules simultaneously based on the non‐negative matrix tri‐factorisation. The experiment results on both synthetic and real‐world biological networks demonstrate that PCNMTF gains more precise functional modules than that of state‐of‐the‐art methods.

A Unified Semi-Supervised Community Detection Framework Using Latent Space Graph Regularization

Community structure is one of the most important properties of complex networks and is a foundational concept in exploring and understanding networks. In real world, topology information alone is often inadequate to accurately find community structure due to its sparsity and noises. However, potential useful prior information can be obtained from domain knowledge in many applications. Thus, how to improve the community detection performance by combining network topology with prior information becomes an interesting and challenging problem. Previous efforts on utilizing such priors are either dedicated or insufficient. In this paper, we firstly present a unified interpretation to a group of existing community detection methods. And then based on this interpretation, we propose a unified semi-supervised framework to integrate network topology with prior information for community detection. If the prior information indicates that some nodes belong to the same community, we encode it by adding a graph regularization term to penalize the latent space dissimilarity of these nodes. This framework can be applied to many widely-used matrix-based community detection methods satisfying our interpretation, such as nonnegative matrix factorization, spectral clustering, and their variants. Extensive experiments on both synthetic and real networks show that the proposed framework significantly improves the accuracy of community detection, especially on networks with unclear structures.

Overlapping community detection using Bayesian non-negative matrix factorization

Identifying overlapping communities in networks is a challenging task. In this work we present a probabilistic approach to community detection that utilizes a Bayesian non-negative matrix factorization model to extract overlapping modules from a network. The scheme has the advantage of soft-partitioning solutions, assignment of node participation scores to modules, and an intuitive foundation. We present the performance of the method against a variety of benchmark problems and compare and contrast it to several other algorithms for community detection.