Fast computing betweenness centrality with virtual nodes on large sparse networks

Betweenness centrality is an essential index for analysis of complex networks. However, the calculation of betweenness centrality is quite time-consuming and the fastest known algorithm uses O(N(M + N log N)) time and O(N + M) space for weighted networks, where N and M are the number of nodes and edges in the network, respectively. By inserting virtual nodes into the weighted edges and transforming the shortest path problem into a breadth-first search (BFS) problem, we propose an algorithm that can compute the betweenness centrality in O(wDN2) time for integer-weighted networks, where w is the average weight of edges and D is the average degree in the network. Considerable time can be saved with the proposed algorithm when w < log N/D + 1, indicating that it is suitable for lightly weighted large sparse networks. A similar concept of virtual node transformation can be used to calculate other shortest path based indices such as closeness centrality, graph centrality, stress centrality, and so on. Numerical simulations on various randomly generated networks reveal that it is feasible to use the proposed algorithm in large network analysis.     

The organisational structure of protein networks: revisiting the centrality–lethality hypothesis

Protein networks, describing physical interactions as well as functional associations between proteins, have been unravelled for many organisms in the recent past. Databases such as the STRING provide excellent resources for the analysis of such networks. In this contribution, we revisit the organisation of protein networks, particularly the centrality–lethality hypothesis, which hypothesises that nodes with higher centrality in a network are more likely to produce lethal phenotypes on removal, compared to nodes with lower centrality. We consider the protein networks of a diverse set of 20 organisms, with essentiality information available in the Database of Essential Genes and assess the relationship between centrality measures and lethality. For each of these organisms, we obtained networks of high-confidence interactions from the STRING database, and computed network parameters such as degree, betweenness centrality, closeness centrality and pairwise disconnectivity indices. We observe that the networks considered here are predominantly disassortative. Further, we observe that essential nodes in a network have a significantly higher average degree and betweenness centrality, compared to the network average. Most previous studies have evaluated the centrality–lethality hypothesis for Saccharomyces cerevisiae and Escherichia coli; we here observe that the centrality–lethality hypothesis hold goods for a large number of organisms, with certain limitations. Betweenness centrality may also be a useful measure to identify essential nodes, but measures like closeness centrality and pairwise disconnectivity are not significantly higher for essential nodes.     

Discovering functions and revealing mechanisms at molecular level from biological networks

With the increasingly accumulated data from high-throughput technologies, study on biomolecular networks has become one of key focuses in systems biology and bioinformatics. In particular, various types of molecular networks (e.g., protein-protein interaction (PPI) network; gene regulatory network (GRN); metabolic network (MN); gene coexpression network (GCEN)) have been extensively investigated, and those studies demonstrate great potentials to discover basic functions and to reveal essential mechanisms for various biological phenomena, by understanding biological systems not at individual component level but at a system-wide level. Recent studies on networks have created very prolific researches on many aspects of living organisms. In this paper, we aim to review the recent developments on topics related to molecular networks in a comprehensive manner, with the special emphasis on the computational aspect. The contents of the survey cover global topological properties and local structural characteristics, network motifs, network comparison and query, detection of functional modules and network motifs, function prediction from network analysis, inferring molecular networks from biological data as well as representative databases and software tools.     

Noise transmission during the dynamic pattern formation in fly embryos

Background: Developmental patterning is highly reproducible and accurate at the single-cell level during fly embryogenesis despite the gene expression noise and external perturbations such as the variation of the embryo length, temperature and genes. To reveal the underlying mechanism, it is very important to characterize the noise transmission during the dynamic pattern formation. Two hypotheses have been proposed. The “channel” scenario requires a highly reproducible input and an accurate interpretation by downstream genes. In contrast, the “filter” scenario proposes a noisy input and a noise filter via the cross-regulation of the downstream network. It has been under great debates which scenario the fly embryogenesis follows. Results: The first 3-h developmental patterning of fly embryos is orchestrated by a hierarchical segmentation gene network, which rewires upon the maternal to zygotic transition. Starting from the highly reproducible maternal gradients, the positional information is refined to the single-cell precision through the highly dynamical evolved zygotic gene expression profiles. Thus the fly embryo development might strictly fit into neither the originally proposed “filter” nor “channel” scenario. The controversy that which scenario the fly embryogenesis follows could be further clarified by combining quantitative measurements and modeling. Conclusions: Fly embryos have become one of the perfect model systems for quantitative systems biology studies. The underlying mechanism discovered from fly embryogenesis will deepen our understanding of the noise control of the gene network, facilitate searching for more efficient and safer methods for cell programming and reprogramming, and have the great potential for tissue engineering and regenerative medicine.     

艺术体操运动员及场馆运动设备的真菌群落组成多样性及关联分析

体操运动员及运动设备的真菌群落组成的多样性,及安全风险研究是涉及公共安全及健康的重要课题。本研究在某体育学院37名平均年龄为19.5岁的艺术体操运动员进行训练后,现场采集手掌、脚跟、运动员的脚尖鞋腔、球、圈、把杆及地毯样本,基于rDNA-ITS的高通量测序,对上述各样本进行了真菌群落组成差异、α-多样性、各样本间共存属及独特属的分布以及样本与物种间的关联分析。结果表明,供试样本的分类单元涉及子囊菌门Ascomycota、担子菌门Basidiomycota、壶菌门Chytridiomycota和接合菌门Zygomycota共4门22纲57目。所测样本中,手掌的优势属为网孢盘菌属Aleuria,相对多度为84.9%;鞋腔的优势属为念珠菌属Candida,相对多度为17.55%;地毯的优势属为交链孢属Alternaria,相对多度为50.9%;把杆的优势属为小大卫霉科Davidiellaceae中的未定属;球（E）和圈（F）群落组成的相对多度分布则较均匀。α-多样性分析结果表明把杆（G）的真菌多样性最高（3.54）,其次为鞋腔（D）（3.18）,再其次为圈（F）（3.13）。样本间共存属及独特属的Venn图解析表明,手掌（A）、脚跟（B）、地毯（C）、鞋腔（D）、球（E）及把杆（G）6个样本上只有一个共存属,即小大卫霉科的一未定属。两个样本间的共存属中,G+D和G+E（分别为27和24个属）比较多。在独特种上,把杆（G）最高,鞋腔（D）和球（E）次之,其余独特属的数量均未超过10个。样本及物种间的关联分析表明,把杆（G）在3个中心度的测度中都处于最高值：度中心度（degree centrality）,0.793;接近中心度（closeness centrality）,0.715;中介中心度（betweenness centrality）,0.754。在体操房运动员与器械构成的网络中,把杆是处于网络中心;随后是器械球（E）和运动员的鞋腔（D）,在度中心度和中介中心度最低的是样本手掌（A）和地毯（C）,其测度分别仅为0.077和0.048;0.053和0.001。研究结论为：（1）测试样本间真菌群落组成差异十分明显,其中把杆、鞋腔、球和圈的群落组成丰富,而地毯和手掌则相对贫乏;（2）把杆的真菌组成种类较多,含有多种潜在的人体病原真菌;（3）艺术体操场馆中地毯、把杆是多种潜在病原真菌的共同载体,它们涉及的公共卫生安全,值得高度关注。     

Gastric cancer biomarkers; A systems biology approach

Gastric cancer is one of the most fatal cancers in the world. Many efforts in recent years have attempted to find effective proteins in gastric cancer. By using a comprehensive list of proteins involved in gastric cancer, scientists were able to retrieve interaction information. The study of protein-protein interaction networks through systems biology based analysis provides appropriate strategies to discover candidate proteins and key biological pathways.In this study, we investigated dominant functional themes and centrality parameters including betweenness as well as the degree of each topological clusters and expressionally active sub-networks in the resulted network. The results of functional analysis on gene sets showed that neurotrophin signaling pathway, cell cycle and nucleotide excision possess the strongest enrichment signals. According to the computed centrality parameters, HNF4A, TAF1 and TP53 manifested as the most significant nodes in the interaction network of the engaged proteins in gastric cancer. This study also demonstrates pathways and proteins that are applicable as diagnostic markers and therapeutic targets for future attempts to overcome gastric cancer.     

Sentiment Diffusion of Public Opinions about Hot Events: Based on Complex Network

To study the sentiment diffusion of online public opinions about hot events, we collected people’s posts through web data mining techniques. We calculated the sentiment value of each post based on a sentiment dictionary. Next, we divided those posts into five different orientations of sentiments: strongly positive (P), weakly positive (p), neutral (o), weakly negative (n), and strongly negative (N). These sentiments are combined into modes through coarse graining. We constructed sentiment mode complex network of online public opinions (SMCOP) with modes as nodes and the conversion relation in chronological order between different types of modes as edges. We calculated the strength, k-plex clique, clustering coefficient and betweenness centrality of the SMCOP. The results show that the strength distribution obeys power law. Most posts’ sentiments are weakly positive and neutral, whereas few are strongly negative. There are weakly positive subgroups and neutral subgroups with ppppp and ooooo as the core mode, respectively. Few modes have larger betweenness centrality values and most modes convert to each other with these higher betweenness centrality modes as mediums. Therefore, the relevant person or institutes can take measures to lead people’s sentiments regarding online hot events according to the sentiment diffusion mechanism.     

Failure tolerance of motif structure in biological networks

Complex networks serve as generic models for many biological systems that have been shown to share a number of common structural properties such as power-law degree distribution and small-worldness. Real-world networks are composed of building blocks called motifs that are indeed specific subgraphs of (usually) small number of nodes. Network motifs are important in the functionality of complex networks, and the role of some motifs such as feed-forward loop in many biological networks has been heavily studied. On the other hand, many biological networks have shown some degrees of robustness in terms of their efficiency and connectedness against failures in their components. In this paper we investigated how random and systematic failures in the edges of biological networks influenced their motif structure. We considered two biological networks, namely, protein structure network and human brain functional network. Furthermore, we considered random failures as well as systematic failures based on different strategies for choosing candidate edges for removal. Failure in the edges tipping to high degree nodes had the most destructive role in the motif structure of the networks by decreasing their significance level, while removing edges that were connected to nodes with high values of betweenness centrality had the least effect on the significance profiles. In some cases, the latter caused increase in the significance levels of the motifs.     

Terahertz vibrational properties of water nanoclusters relevant to biology

Water nanoclusters are shown from first-principles calculations to possess unique terahertz-frequency vibrational modes in the 1–6 THz range, corresponding to O–O–O “bending,” “squashing,” and “twisting” “surface” distortions of the clusters. The cluster molecular-orbital LUMOs are huge Rydberg-like “S,” “P,” “D,” and “F” orbitals that accept an extra electron via optical excitation, ionization, or electron donation from interacting biomolecules. Dynamic Jahn–Teller coupling of these “hydrated-electron” orbitals to the THz vibrations promotes such water clusters as vibronically active “structured water” essential to biomolecular function such as protein folding. In biological microtubules, confined water-cluster THz vibrations may induce their “quantum coherence” communicated by Jahn–Teller phonons via coupling of the THz electromagnetic field to the water clusters’ large electric dipole moments.     

Eigenvector Centrality Mapping for Analyzing Connectivity Patterns in fMRI Data of the Human Brain

Functional magnetic resonance data acquired in a task-absent condition (“resting state”) require new data analysis techniques that do not depend on an activation model. In this work, we introduce an alternative assumption- and parameter-free method based on a particular form of node centrality called eigenvector centrality. Eigenvector centrality attributes a value to each voxel in the brain such that a voxel receives a large value if it is strongly correlated with many other nodes that are themselves central within the network. Google''s PageRank algorithm is a variant of eigenvector centrality. Thus far, other centrality measures - in particular “betweenness centrality” - have been applied to fMRI data using a pre-selected set of nodes consisting of several hundred elements. Eigenvector centrality is computationally much more efficient than betweenness centrality and does not require thresholding of similarity values so that it can be applied to thousands of voxels in a region of interest covering the entire cerebrum which would have been infeasible using betweenness centrality. Eigenvector centrality can be used on a variety of different similarity metrics. Here, we present applications based on linear correlations and on spectral coherences between fMRI times series. This latter approach allows us to draw conclusions of connectivity patterns in different spectral bands. We apply this method to fMRI data in task-absent conditions where subjects were in states of hunger or satiety. We show that eigenvector centrality is modulated by the state that the subjects were in. Our analyses demonstrate that eigenvector centrality is a computationally efficient tool for capturing intrinsic neural architecture on a voxel-wise level.     

Accelerated search for biomolecular network models to interpret high-throughput experimental data

Background  

The functions of human cells are carried out by biomolecular networks, which include proteins, genes, and regulatory sites within DNA that encode and control protein expression. Models of biomolecular network structure and dynamics can be inferred from high-throughput measurements of gene and protein expression. We build on our previously developed fuzzy logic method for bridging quantitative and qualitative biological data to address the challenges of noisy, low resolution high-throughput measurements, i.e., from gene expression microarrays. We employ an evolutionary search algorithm to accelerate the search for hypothetical fuzzy biomolecular network models consistent with a biological data set. We also develop a method to estimate the probability of a potential network model fitting a set of data by chance. The resulting metric provides an estimate of both model quality and dataset quality, identifying data that are too noisy to identify meaningful correlations between the measured variables.     

Fast Fragmentation of Networks Using Module-Based Attacks

In the multidisciplinary field of Network Science, optimization of procedures for efficiently breaking complex networks is attracting much attention from a practical point of view. In this contribution, we present a module-based method to efficiently fragment complex networks. The procedure firstly identifies topological communities through which the network can be represented using a well established heuristic algorithm of community finding. Then only the nodes that participate of inter-community links are removed in descending order of their betweenness centrality. We illustrate the method by applying it to a variety of examples in the social, infrastructure, and biological fields. It is shown that the module-based approach always outperforms targeted attacks to vertices based on node degree or betweenness centrality rankings, with gains in efficiency strongly related to the modularity of the network. Remarkably, in the US power grid case, by deleting 3% of the nodes, the proposed method breaks the original network in fragments which are twenty times smaller in size than the fragments left by betweenness-based attack.     

Spatial familial networks to infer demographic structure of wild populations

1. In social species, reproductive success and rates of dispersal vary among individuals resulting in spatially structured populations. Network analyses of familial relationships may provide insights on how these parameters influence population‐level demographic patterns. These methods, however, have rarely been applied to genetically derived pedigree data from wild populations.
2. Here, we use parent–offspring relationships to construct familial networks from polygamous boreal woodland caribou (Rangifer tarandus caribou) in Saskatchewan, Canada, to inform recovery efforts. We collected samples from 933 individuals at 15 variable microsatellite loci along with caribou‐specific primers for sex identification. Using network measures, we assess the contribution of individual caribou to the population with several centrality measures and then determine which measures are best suited to inform on the population demographic structure. We investigate the centrality of individuals from eighteen different local areas, along with the entire population.
3. We found substantial differences in centrality of individuals in different local areas, that in turn contributed differently to the full network, highlighting the importance of analyzing networks at different scales. The full network revealed that boreal caribou in Saskatchewan form a complex, interconnected familial network, as the removal of edges with high betweenness did not result in distinct subgroups. Alpha, betweenness, and eccentricity centrality were the most informative measures to characterize the population demographic structure and for spatially identifying areas of highest fitness levels and family cohesion across the range. We found varied levels of dispersal, fitness, and cohesion in family groups.
4. Synthesis and applications: Our results demonstrate the value of different network measures in assessing genetically derived familial networks. The spatial application of the familial networks identified individuals presenting different fitness levels, short‐ and long‐distance dispersing ability across the range in support of population monitoring and recovery efforts.

     

Complexity of the international agro-food trade network and its impact on food safety

With the world's population now in excess of 7 billion, it is vital to ensure the chemical and microbiological safety of our food, while maintaining the sustainability of its production, distribution and trade. Using UN databases, here we show that the international agro-food trade network (IFTN), with nodes and edges representing countries and import-export fluxes, respectively, has evolved into a highly heterogeneous, complex supply-chain network. Seven countries form the core of the IFTN, with high values of betweenness centrality and each trading with over 77% of all the countries in the world. Graph theoretical analysis and a dynamic food flux model show that the IFTN provides a vehicle suitable for the fast distribution of potential contaminants but unsuitable for tracing their origin. In particular, we show that high values of node betweenness and vulnerability correlate well with recorded large food poisoning outbreaks.     

Global Versus Local Centrality in Evolution of Yeast Protein Network

It is shown here that in the yeast protein interaction network the global centrality measure (betweenness) depends on the protein evolutionary age (i.e., on historic contingency) more weakly than the local centrality measure (degree). This phenomenon is not observed in mutational duplication-and-divergence models. The network domains responsible for this difference deal with DNA/RNA information processing, regulation, and cell cycle. A selection vector can operate in these domains, which integrates the network activity and thus compensates for the process of mutational divergence. Electronic supplementary material  The online version of this article (doi:) contains supplementary material, which is available to authorized users.     

Social networks in the Little Scrub Island ground lizard (<Emphasis Type="Italic">Ameiva corax</Emphasis>)

Ameiva corax is a diurnal, widely foraging lizard endemic to a small (<2 ha) Caribbean island and is known for social foraging, whereby individuals aggregate at large food items (e.g., bird eggs and cactus fruits). We characterized the social network for A. corax through focal observations and surveys, which delineated associations for 82 known individuals. Lizards varied greatly in the extent to which they were linked to the social network. Approximately 31 % of individuals were not observed in any associations while one individual associated with 22 % (n = 18) of the animals in the study area. Larger lizards tended to be more central to the social network; body size was positively correlated with number of associations (degree) and centrality (betweenness), but negatively correlated with average distance between an individual and its associates (mean path length). Larger individuals were also associated with lower clustering coefficients, indicating that their associates were less closely interconnected. Sex was not related to number of associations (degree), but did help explain some patterns. The extent to which a lizard’s associates were of the same sex (homophily) was related to both sex and body size. Females had lower homophily scores than males; within each sex larger lizards tended to have lower homophily.     

High-throughput quantification of microbial birth and death dynamics using fluorescence microscopy

Background: Microbes live in dynamic environments where nutrient concentrations fluctuate. Quantifying fitness in terms of birth rate and death rate in a wide range of environments is critical for understanding microbial evolution and ecology. Methods: Here, using high-throughput time-lapse microscopy, we have quantified how Saccharomyces cerevisiae mutants incapable of synthesizing an essential metabolite (auxotrophs) grow or die in various concentrations of the required metabolite. We establish that cells normally expressing fluorescent proteins lose fluorescence upon death and that the total fluorescence in an imaging frame is proportional to the number of live cells even when cells form multiple layers. We validate our microscopy approach of measuring birth and death rates using flow cytometry, cell counting, and chemostat culturing. Results: For lysine-requiring cells, very low concentrations of lysine are not detectably consumed and do not support cell birth, but delay the onset of death phase and reduce the death rate compared to no lysine. In contrast, in low hypoxanthine, hypoxanthine-requiring cells can produce new cells, yet also die faster than in the absence of hypoxanthine. For both strains, birth rates under various metabolite concentrations are better described by the sigmoidal-shaped Moser model than the well-known Monod model, while death rates can vary with metabolite concentration and time. Conclusions: Our work reveals how time-lapse microscopy can be used to discover non-intuitive microbial birth and death dynamics and to quantify growth rates in many environments.