IPCA-CMI: An Algorithm for Inferring Gene Regulatory Networks based on a Combination of PCA-CMI and MIT Score

Inferring gene regulatory networks (GRNs) is a major issue in systems biology, which explicitly characterizes regulatory processes in the cell. The Path Consistency Algorithm based on Conditional Mutual Information (PCA-CMI) is a well-known method in this field. In this study, we introduce a new algorithm (IPCA-CMI) and apply it to a number of gene expression data sets in order to evaluate the accuracy of the algorithm to infer GRNs. The IPCA-CMI can be categorized as a hybrid method, using the PCA-CMI and Hill-Climbing algorithm (based on MIT score). The conditional dependence between variables is determined by the conditional mutual information test which can take into account both linear and nonlinear genes relations. IPCA-CMI uses a score and search method and defines a selected set of variables which is adjacent to one of or Y. This set is used to determine the dependency between X and Y. This method is compared with the method of evaluating dependency by PCA-CMI in which the set of variables adjacent to both X and Y, is selected. The merits of the IPCA-CMI are evaluated by applying this algorithm to the DREAM3 Challenge data sets with n variables and n samples () and to experimental data from Escherichia coil containing 9 variables and 9 samples. Results indicate that applying the IPCA-CMI improves the precision of learning the structure of the GRNs in comparison with that of the PCA-CMI.     

PhysarumSpreader: A New Bio-Inspired Methodology for Identifying Influential Spreaders in Complex Networks

Identifying influential spreaders in networks, which contributes to optimizing the use of available resources and efficient spreading of information, is of great theoretical significance and practical value. A random-walk-based algorithm LeaderRank has been shown as an effective and efficient method in recognizing leaders in social network, which even outperforms the well-known PageRank method. As LeaderRank is initially developed for binary directed networks, further extensions should be studied in weighted networks. In this paper, a generalized algorithm PhysarumSpreader is proposed by combining LeaderRank with a positive feedback mechanism inspired from an amoeboid organism called Physarum Polycephalum. By taking edge weights into consideration and adding the positive feedback mechanism, PhysarumSpreader is applicable in both directed and undirected networks with weights. By taking two real networks for examples, the effectiveness of the proposed method is demonstrated by comparing with other standard centrality measures.     

Parsing Social Network Survey Data from Hidden Populations Using Stochastic Context-Free Grammars

Background

Human populations are structured by social networks, in which individuals tend to form relationships based on shared attributes. Certain attributes that are ambiguous, stigmatized or illegal can create a ÔhiddenÕ population, so-called because its members are difficult to identify. Many hidden populations are also at an elevated risk of exposure to infectious diseases. Consequently, public health agencies are presently adopting modern survey techniques that traverse social networks in hidden populations by soliciting individuals to recruit their peers, e.g., respondent-driven sampling (RDS). The concomitant accumulation of network-based epidemiological data, however, is rapidly outpacing the development of computational methods for analysis. Moreover, current analytical models rely on unrealistic assumptions, e.g., that the traversal of social networks can be modeled by a Markov chain rather than a branching process.

Methodology/Principal Findings

Here, we develop a new methodology based on stochastic context-free grammars (SCFGs), which are well-suited to modeling tree-like structure of the RDS recruitment process. We apply this methodology to an RDS case study of injection drug users (IDUs) in Tijuana, México, a hidden population at high risk of blood-borne and sexually-transmitted infections (i.e., HIV, hepatitis C virus, syphilis). Survey data were encoded as text strings that were parsed using our custom implementation of the inside-outside algorithm in a publicly-available software package (HyPhy), which uses either expectation maximization or direct optimization methods and permits constraints on model parameters for hypothesis testing. We identified significant latent variability in the recruitment process that violates assumptions of Markov chain-based methods for RDS analysis: firstly, IDUs tended to emulate the recruitment behavior of their own recruiter; and secondly, the recruitment of like peers (homophily) was dependent on the number of recruits.

Conclusions

SCFGs provide a rich probabilistic language that can articulate complex latent structure in survey data derived from the traversal of social networks. Such structure that has no representation in Markov chain-based models can interfere with the estimation of the composition of hidden populations if left unaccounted for, raising critical implications for the prevention and control of infectious disease epidemics.     

Active Semi-Supervised Community Detection Based on Must-Link and Cannot-Link Constraints

Community structure detection is of great importance because it can help in discovering the relationship between the function and the topology structure of a network. Many community detection algorithms have been proposed, but how to incorporate the prior knowledge in the detection process remains a challenging problem. In this paper, we propose a semi-supervised community detection algorithm, which makes full utilization of the must-link and cannot-link constraints to guide the process of community detection and thereby extracts high-quality community structures from networks. To acquire the high-quality must-link and cannot-link constraints, we also propose a semi-supervised component generation algorithm based on active learning, which actively selects nodes with maximum utility for the proposed semi-supervised community detection algorithm step by step, and then generates the must-link and cannot-link constraints by accessing a noiseless oracle. Extensive experiments were carried out, and the experimental results show that the introduction of active learning into the problem of community detection makes a success. Our proposed method can extract high-quality community structures from networks, and significantly outperforms other comparison methods.     

Evolution Characteristics of the Network Core in the Facebook

Statistical properties of the static networks have been extensively studied. However, online social networks are evolving dynamically, understanding the evolving characteristics of the core is one of major concerns in online social networks. In this paper, we empirically investigate the evolving characteristics of the Facebook core. Firstly, we separate the Facebook-link(FL) and Facebook-wall(FW) datasets into 28 snapshots in terms of timestamps. By employing the k-core decomposition method to identify the core of each snapshot, we find that the core sizes of the FL and FW networks approximately contain about 672 and 373 nodes regardless of the exponential growth of the network sizes. Secondly, we analyze evolving topological properties of the core, including the k-core value, assortative coefficient, clustering coefficient and the average shortest path length. Empirical results show that nodes in the core are getting more interconnected in the evolving process. Thirdly, we investigate the life span of nodes belonging to the core. More than 50% nodes stay in the core for more than one year, and 19% nodes always stay in the core from the first snapshot. Finally, we analyze the connections between the core and the whole network, and find that nodes belonging to the core prefer to connect nodes with high k-core values, rather than the high degrees ones. This work could provide new insights into the online social network analysis.     

Chimpanzee identification and social network construction through an online citizen science platform

Citizen science has grown rapidly in popularity in recent years due to its potential to educate and engage the public while providing a means to address a myriad of scientific questions. However, the rise in popularity of citizen science has also been accompanied by concerns about the quality of data emerging from citizen science research projects. We assessed data quality in the online citizen scientist platform Chimp&See, which hosts camera trap videos of chimpanzees (Pan troglodytes) and other species across Equatorial Africa. In particular, we compared detection and identification of individual chimpanzees by citizen scientists with that of experts with years of experience studying those chimpanzees. We found that citizen scientists typically detected the same number of individual chimpanzees as experts, but assigned far fewer identifications (IDs) to those individuals. Those IDs assigned, however, were nearly always in agreement with the IDs provided by experts. We applied the data sets of citizen scientists and experts by constructing social networks from each. We found that both social networks were relatively robust and shared a similar structure, as well as having positively correlated individual network positions. Our findings demonstrate that, although citizen scientists produced a smaller data set based on fewer confirmed IDs, the data strongly reflect expert classifications and can be used for meaningful assessments of group structure and dynamics. This approach expands opportunities for social research and conservation monitoring in great apes and many other individually identifiable species.     

Identifying protein complexes from interaction networks based on clique percolation and distance restriction

Background

Identification of protein complexes in large interaction networks is crucial to understand principles of cellular organization and predict protein functions, which is one of the most important issues in the post-genomic era. Each protein might be subordinate multiple protein complexes in the real protein-protein interaction networks. Identifying overlapping protein complexes from protein-protein interaction networks is a considerable research topic.

Result

As an effective algorithm in identifying overlapping module structures, clique percolation method (CPM) has a wide range of application in social networks and biological networks. However, the recognition accuracy of algorithm CPM is lowly. Furthermore, algorithm CPM is unfit to identifying protein complexes with meso-scale when it applied in protein-protein interaction networks. In this paper, we propose a new topological model by extending the definition of k-clique community of algorithm CPM and introduced distance restriction, and develop a novel algorithm called CP-DR based on the new topological model for identifying protein complexes. In this new algorithm, the protein complex size is restricted by distance constraint to conquer the shortcomings of algorithm CPM. The algorithm CP-DR is applied to the protein interaction network of Sacchromyces cerevisiae and identifies many well known complexes.

Conclusion

The proposed algorithm CP-DR based on clique percolation and distance restriction makes it possible to identify dense subgraphs in protein interaction networks, a large number of which correspond to known protein complexes. Compared to algorithm CPM, algorithm CP-DR has more outstanding performance.

     

Cooperation prevails when individuals adjust their social ties

Conventional evolutionary game theory predicts that natural selection favours the selfish and strong even though cooperative interactions thrive at all levels of organization in living systems. Recent investigations demonstrated that a limiting factor for the evolution of cooperative interactions is the way in which they are organized, cooperators becoming evolutionarily competitive whenever individuals are constrained to interact with few others along the edges of networks with low average connectivity. Despite this insight, the conundrum of cooperation remains since recent empirical data shows that real networks exhibit typically high average connectivity and associated single-to-broad–scale heterogeneity. Here, a computational model is constructed in which individuals are able to self-organize both their strategy and their social ties throughout evolution, based exclusively on their self-interest. We show that the entangled evolution of individual strategy and network structure constitutes a key mechanism for the sustainability of cooperation in social networks. For a given average connectivity of the population, there is a critical value for the ratio W between the time scales associated with the evolution of strategy and of structure above which cooperators wipe out defectors. Moreover, the emerging social networks exhibit an overall heterogeneity that accounts very well for the diversity of patterns recently found in acquired data on social networks. Finally, heterogeneity is found to become maximal when W reaches its critical value. These results show that simple topological dynamics reflecting the individual capacity for self-organization of social ties can produce realistic networks of high average connectivity with associated single-to-broad–scale heterogeneity. On the other hand, they show that cooperation cannot evolve as a result of “social viscosity” alone in heterogeneous networks with high average connectivity, requiring the additional mechanism of topological co-evolution to ensure the survival of cooperative behaviour.     

Using data from online social networks in conservation science: which species engage people the most on Twitter?

Knowledge about the level of public attention toward different species is crucial to successful conservation. The evolution of online social networks offers new possibilities for collecting data about public interest. Building on an analysis of text messages on Twitter, this study aimed to quantify the level of public attention toward different mammal and bird species listed (at the full species or subspecies/population level) under the United States’ Endangered Species Act (ESA). Once a month during 1 year, I searched recently posted messages (‘tweets’) for the common names of every listed species. The polar bear (Ursus maritimus) was by far the most tweeted species. The other most tweeted mammals were the American bison (Bison bison), brown bear (U. arctos), cougar (Puma concolor), killer whale (Orcinus orca), black bear (U. americanus) and West Indian manatee (Trichechus manatus), respectively. The three most frequently tweeted birds were the sandhill crane (Grus canadensis), whooping crane (G. americana) and spotted owl (Strix occidentalis). Some species, such as the manatee, right whale (Eubalaena glacialis), and gray wolf (Canis lupus) ranked higher when restricting the search to conservation contexts. The results suggest that Twitter users interact about a biased sample of ESA-listed species: mammals were better represented than birds among the most tweeted species and larger-sized species received more tweets. The findings can be used for prioritizing conservation education and marketing campaigns aiming to raise the profile of lesser-known listed species. Data from online social networks open the door for a range of novel applications in conservation science.     

Discovery of candidate genes for heterosis breeding in <Emphasis Type="Italic">Brassica oleracea</Emphasis> L.

Heterosis is very important for hybrid breeding and productivity of various crop plants can be increased easily by exploitation of it. However, the molecular basis of heterosis has yet to be elucidated. In this study, 51 heterosis-associated genes of different families of Arabidopsis were selected based on their high differential expression in a hybrid relative to its mid-parent value and their orthologues were identified in Brassica oleracea. The selected B. oleracea genes were then characterized based on their predicted functions and expression patterns in four parent-hybrid combinations of cabbage. Many of these genes were found to be more highly expressed in the hybrid than the mid-parent value, and some were better in the parent. Moreover, these highly expressed genes were mostly related to the yield contributing characteristics. Cotyledon and young leaf sizes of these three genotypes were also well correlated with responsive expression of genes analyzed in the parent–hybrid combinations. Thus, the identified genes might be associated with the mechanism of heterosis of B. oleracea hybrid and provide a foundation to reveal the complexity of regulatory gene networks associated with genetic mechanism of heterosis in the plant life cycle. Subsequently, these genes would be useful resources for molecular breeding of hybrid Brassica crops, as well.     

Detecting controlling nodes of boolean regulatory networks

Boolean models of regulatory networks are assumed to be tolerant to perturbations. That qualitatively implies that each function can only depend on a few nodes. Biologically motivated constraints further show that functions found in Boolean regulatory networks belong to certain classes of functions, for example, the unate functions. It turns out that these classes have specific properties in the Fourier domain. That motivates us to study the problem of detecting controlling nodes in classes of Boolean networks using spectral techniques. We consider networks with unbalanced functions and functions of an average sensitivity less than ?k, where k is the number of controlling variables for a function. Further, we consider the class of 1-low networks which include unate networks, linear threshold networks, and networks with nested canalyzing functions. We show that the application of spectral learning algorithms leads to both better time and sample complexity for the detection of controlling nodes compared with algorithms based on exhaustive search. For a particular algorithm, we state analytical upper bounds on the number of samples needed to find the controlling nodes of the Boolean functions. Further, improved algorithms for detecting controlling nodes in large-scale unate networks are given and numerically studied.     

Properties of Normal Phylogenetic Networks

A phylogenetic network is a rooted acyclic digraph with vertices corresponding to taxa. Let X denote a set of vertices containing the root, the leaves, and all vertices of outdegree 1. Regard X as the set of vertices on which measurements such as DNA can be made. A vertex is called normal if it has one parent, and hybrid if it has more than one parent. The network is called normal if it has no redundant arcs and also from every vertex there is a directed path to a member of X such that all vertices after the first are normal. This paper studies properties of normal networks. Under a simple model of inheritance that allows homoplasies only at hybrid vertices, there is essentially unique determination of the genomes at all vertices by the genomes at members of X if and only if the network is normal. This model is a limiting case of more standard models of inheritance when the substitution rate is sufficiently low. Various mathematical properties of normal networks are described. These properties include that the number of vertices grows at most quadratically with the number of leaves and that the number of hybrid vertices grows at most linearly with the number of leaves.     

Detecting overlapping protein complexes in PPI networks based on robustness

Background

Recently, large data sets of protein-protein interactions (PPI) which can be modeled as PPI networks are generated through high-throughput methods. And locally dense regions in PPI networks are very likely to be protein complexes. Since protein complexes play a key role in many biological processes, detecting protein complexes in PPI networks is one of important tasks in post-genomic era. However, PPI networks are often incomplete and noisy, which builds barriers to mining protein complexes.

Results

We propose a new and effective algorithm based on robustness to detect overlapping clusters as protein complexes in PPI networks. And in order to improve the accuracy of resulting clusters, our algorithm tries to reduce bad effects brought by noise in PPI networks. And in our algorithm, each new cluster begins from a seed and is expanded through adding qualified nodes from the cluster's neighbourhood nodes. Besides, in our algorithm, a new distance measurement method between a cluster K and a node in the neighbours of K is proposed as well. The performance of our algorithm is evaluated by applying it on two PPI networks which are Gavin network and Database of Interacting Proteins (DIP). The results show that our algorithm is better than Markov clustering algorithm (MCL), Clique Percolation method (CPM) and core-attachment based method (CoAch) in terms of F-measure, co-localization and Gene Ontology (GO) semantic similarity.

Conclusions

Our algorithm detects locally dense regions or clusters as protein complexes. The results show that protein complexes generated by our algorithm have better quality than those generated by some previous classic methods. Therefore, our algorithm is effective and useful.

     

Hatchery practices may result in replacement of wild salmonids: adult trends in the Klamath basin,California

Appraisal of hatchery-related effects on Pacific salmonids (Oncorhynchus spp.) is a necessary component of species conservation. For example, hatchery supplementation can influence species viability by changing genetic, phenotypic and life-history diversity. We analyzed time series data for seven salmonid taxa from the Klamath River basin, California, to investigate trajectories of wild and hatchery adult populations. Linear regression coupled with randomized permutations (n?=?99,999), two- tailed t tests, and Bayesian change point analysis were used to detect trends over time. Cross correlation was also used to evaluate relationships between wild and hatchery populations. The taxa of interest were spring, fall, and late-fall Chinook Salmon (O. tshawytscha); Coho Salmon (O. kisutch); Coastal Cutthroat Trout (O. clarki clarki); and summer and hybrid Steelhead Trout (O. mykiss). Significant decreases were detected for summer and hybrid Steelhead Trout. The proportion of wild fall Chinook has also significantly decreased concurrently with increases in hatchery returns. In comparison, returns of most Chinook and coho runs to the hatcheries, and fall Chinook strays to wild spawning areas from Iron Gate Hatchery have significantly increased since the 1970s. Increases were also detected for wild late-fall Chinook and spring Chinook adults. However, both of these were significantly correlated with Chinook Salmon returns to Trinity River Hatchery, suggesting augmentation by hatchery strays. Changes in abundances appeared related to changing ocean habitat conditions and hatchery practices. Our results suggest that anadromous salmonid populations in the Klamath River basin are becoming increasingly dependent on hatchery propagation, a pattern that can threaten population persistence.     

Rapid pedobarographic image registration based on contour curvature and optimization

Image registration, the process of optimally aligning homologous structures in multiple images, has recently been demonstrated to support automated pixel-level analysis of pedobarographic images and, subsequently, to extract unique and biomechanically relevant information from plantar pressure data. Recent registration methods have focused on robustness, with slow but globally powerful algorithms. In this paper, we present an alternative registration approach that affords both speed and accuracy, with the goal of making pedobarographic image registration more practical for near-real-time laboratory and clinical applications. The current algorithm first extracts centroid-based curvature trajectories from pressure image contours, and then optimally matches these curvature profiles using optimization based on dynamic programming. Special cases of disconnected images (that occur in high-arched subjects, for example) are dealt with by introducing an artificial spatially linear bridge between adjacent image clusters. Two registration algorithms were developed: a ‘geometric’ algorithm, which exclusively matched geometry, and a ‘hybrid’ algorithm, which performed subsequent pseudo-optimization. After testing the two algorithms on 30 control image pairs considered in a previous study, we found that, when compared with previously published results, the hybrid algorithm improved overlap ratio (p=0.010), but both current algorithms had slightly higher mean-squared error, assumedly because they did not consider pixel intensity. Nonetheless, both algorithms greatly improved the computational efficiency (25±8 and 53±9 ms per image pair for geometric and hybrid registrations, respectively). These results imply that registration-based pixel-level pressure image analyses can, eventually, be implemented for practical clinical purposes.     

Healthcare Worker Contact Networks and the Prevention of Hospital-Acquired Infections

We present a comprehensive approach to using electronic medical records (EMR) for constructing contact networks of healthcare workers in a hospital. This approach is applied at the University of Iowa Hospitals and Clinics (UIHC) – a 3.2 million square foot facility with 700 beds and about 8,000 healthcare workers – by obtaining 19.8 million EMR data points, spread over more than 21 months. We use these data to construct 9,000 different healthcare worker contact networks, which serve as proxies for patterns of actual healthcare worker contacts. Unlike earlier approaches, our methods are based on large-scale data and do not make any a priori assumptions about edges (contacts) between healthcare workers, degree distributions of healthcare workers, their assignment to wards, etc. Preliminary validation using data gathered from a 10-day long deployment of a wireless sensor network in the Medical Intensive Care Unit suggests that EMR logins can serve as realistic proxies for hospital-wide healthcare worker movement and contact patterns. Despite spatial and job-related constraints on healthcare worker movement and interactions, analysis reveals a strong structural similarity between the healthcare worker contact networks we generate and social networks that arise in other (e.g., online) settings. Furthermore, our analysis shows that disease can spread much more rapidly within the constructed contact networks as compared to random networks of similar size and density. Using the generated contact networks, we evaluate several alternate vaccination policies and conclude that a simple policy that vaccinates the most mobile healthcare workers first, is robust and quite effective relative to a random vaccination policy.     

Social networks based on frequency of roost cohabitation do not reflect association rates of Myotis lucifugus within their roosts

Bats are a group of mammals well known for forming dynamic social groups. Studies of bat social structures are often based upon the frequency at which bats occupy the same roosts because observing bats directly is not always possible. However, it is not always clear how closely bats occupying the same roost associate with each other, obscuring whether associations result from social relationships or factors such as shared preferences for roosts. Our goal was to determine if bats cohabitating buildings were also found together inside roosts by using anti‐collision technology for PIT tags, which enables simultaneous detection of multiple tags. We PIT‐tagged 293 female little brown myotis (Myotis lucifugus) and installed antennas within two buildings used as maternity roosts in Yellowstone National Park. Antennas were positioned at roost entryways to generate cohabitation networks and along regions of attic ceilings in each building to generate intraroost networks based on proximity of bats to each other. We found that intraroost and cohabitation networks of buildings were significantly correlated, with the same bats tending to be linked in both networks, but that bats cohabitating the same building often roosted apart, leading to differing assessments of social structure. Cohabitation rates implied that bats associate with a greater number of their roost‐mates than was supported by observations within the roost. This caused social networks built upon roost cohabitation rates to be denser, smaller in diameter, and contain nodes with higher average degree centrality. These results show that roost cohabitation does not reflect preference for roost‐mates in little brown myotis, as is often inferred from similar studies, and that social network analyses based on cohabitation may provide misleading results.