From knockouts to networks: establishing direct cause-effect relationships through graph analysis

Background

Reverse-engineering gene networks from expression profiles is a difficult problem for which a multitude of techniques have been developed over the last decade. The yearly organized DREAM challenges allow for a fair evaluation and unbiased comparison of these methods.

Results

We propose an inference algorithm that combines confidence matrices, computed as the standard scores from single-gene knockout data, with the down-ranking of feed-forward edges. Substantial improvements on the predictions can be obtained after the execution of this second step.

Conclusions

Our algorithm was awarded the best overall performance at the DREAM4 In Silico 100-gene network sub-challenge, proving to be effective in inferring medium-size gene regulatory networks. This success demonstrates once again the decisive importance of gene expression data obtained after systematic gene perturbations and highlights the usefulness of graph analysis to increase the reliability of inference.     

An Algorithm for Network-Based Gene Prioritization That Encodes Knowledge Both in Nodes and in Links

Background

Candidate gene prioritization aims to identify promising new genes associated with a disease or a biological process from a larger set of candidate genes. In recent years, network-based methods – which utilize a knowledge network derived from biological knowledge – have been utilized for gene prioritization. Biological knowledge can be encoded either through the network''s links or nodes. Current network-based methods can only encode knowledge through links. This paper describes a new network-based method that can encode knowledge in links as well as in nodes.

Results

We developed a new network inference algorithm called the Knowledge Network Gene Prioritization (KNGP) algorithm which can incorporate both link and node knowledge. The performance of the KNGP algorithm was evaluated on both synthetic networks and on networks incorporating biological knowledge. The results showed that the combination of link knowledge and node knowledge provided a significant benefit across 19 experimental diseases over using link knowledge alone or node knowledge alone.

Conclusions

The KNGP algorithm provides an advance over current network-based algorithms, because the algorithm can encode both link and node knowledge. We hope the algorithm will aid researchers with gene prioritization.     

Network 'small-world-ness': a quantitative method for determining canonical network equivalence

Background

Many technological, biological, social, and information networks fall into the broad class of ‘small-world’ networks: they have tightly interconnected clusters of nodes, and a shortest mean path length that is similar to a matched random graph (same number of nodes and edges). This semi-quantitative definition leads to a categorical distinction (‘small/not-small’) rather than a quantitative, continuous grading of networks, and can lead to uncertainty about a network''s small-world status. Moreover, systems described by small-world networks are often studied using an equivalent canonical network model – the Watts-Strogatz (WS) model. However, the process of establishing an equivalent WS model is imprecise and there is a pressing need to discover ways in which this equivalence may be quantified.

Methodology/Principal Findings

We defined a precise measure of ‘small-world-ness’ S based on the trade off between high local clustering and short path length. A network is now deemed a ‘small-world’ if S>1 - an assertion which may be tested statistically. We then examined the behavior of S on a large data-set of real-world systems. We found that all these systems were linked by a linear relationship between their S values and the network size n. Moreover, we show a method for assigning a unique Watts-Strogatz (WS) model to any real-world network, and show analytically that the WS models associated with our sample of networks also show linearity between S and n. Linearity between S and n is not, however, inevitable, and neither is S maximal for an arbitrary network of given size. Linearity may, however, be explained by a common limiting growth process.

Conclusions/Significance

We have shown how the notion of a small-world network may be quantified. Several key properties of the metric are described and the use of WS canonical models is placed on a more secure footing.     

Speech graphs provide a quantitative measure of thought disorder in psychosis

Background

Psychosis has various causes, including mania and schizophrenia. Since the differential diagnosis of psychosis is exclusively based on subjective assessments of oral interviews with patients, an objective quantification of the speech disturbances that characterize mania and schizophrenia is in order. In principle, such quantification could be achieved by the analysis of speech graphs. A graph represents a network with nodes connected by edges; in speech graphs, nodes correspond to words and edges correspond to semantic and grammatical relationships.

Methodology/Principal Findings

To quantify speech differences related to psychosis, interviews with schizophrenics, manics and normal subjects were recorded and represented as graphs. Manics scored significantly higher than schizophrenics in ten graph measures. Psychopathological symptoms such as logorrhea, poor speech, and flight of thoughts were grasped by the analysis even when verbosity differences were discounted. Binary classifiers based on speech graph measures sorted schizophrenics from manics with up to 93.8% of sensitivity and 93.7% of specificity. In contrast, sorting based on the scores of two standard psychiatric scales (BPRS and PANSS) reached only 62.5% of sensitivity and specificity.

Conclusions/Significance

The results demonstrate that alterations of the thought process manifested in the speech of psychotic patients can be objectively measured using graph-theoretical tools, developed to capture specific features of the normal and dysfunctional flow of thought, such as divergence and recurrence. The quantitative analysis of speech graphs is not redundant with standard psychometric scales but rather complementary, as it yields a very accurate sorting of schizophrenics and manics. Overall, the results point to automated psychiatric diagnosis based not on what is said, but on how it is said.     

The Topology of a Discussion: The #Occupy Case

Introduction

We analyse a large sample of the Twitter activity that developed around the social movement ''Occupy Wall Street'', to study the complex interactions between the human communication activity and the semantic content of a debate.

Methods

We use a network approach based on the analysis of the bipartite graph @Users-#Hashtags and of its projections: the ''semantic network'', whose nodes are hashtags, and the ''users interest network'', whose nodes are users. In the first instance, we find out that discussion topics (#hashtags) present a high structural heterogeneity, with a relevant role played by the semantic hubs that are responsible to guarantee the continuity of the debate. In the users’ case, the self-organisation process of users’ activity, leads to the emergence of two classes of communicators: the ''professionals'' and the ''amateurs''.

Results

Both the networks present a strong community structure, based on the differentiation of the semantic topics, and a high level of structural robustness when certain sets of topics are censored and/or accounts are removed.

Conclusions

By analysing the characteristics of the dynamical networks we can distinguish three phases of the discussion about the movement. Each phase corresponds to a specific moment of the movement: from declaration of intent, organisation and development and the final phase of political reactions. Each phase is characterised by the presence of prototypical #hashtags in the discussion.     

First-Episode Medication-Naive Major Depressive Disorder Is Associated with Altered Resting Brain Function in the Affective Network

Background

Major depressive disorder (MDD) has been associated with abnormal structure and function of the brain''s affective network, including the amygdala and orbitofrontal cortex (OFC). However, it is unclear if alterations of resting-state function in this affective network are present at the initial onset of MDD.

Aims

To examine resting-state function of the brain''s affective network in first-episode, medication-naive patients with MDD compared to healthy controls (HCs).

Methods

Resting-state functional magnetic resonance imaging (rs-fMRI) was performed on 32 first-episode, medication-naive young adult patients with MDD and 35 matched HCs. The amplitude of low-frequency fluctuations (ALFF) of the blood oxygen level-dependent (BOLD) signal and amygdala-seeded functional connectivity (FC) were investigated.

Results

Compared to HC, MDD patients showed reduced ALFF in the bilateral OFC and increased ALFF in the bilateral temporal lobe extending to the insular and left fusiform cortices. Enhanced anti-correlation of activity between the left amygdala seed and the left OFC was found in MDD patients but not in HCs.

Conclusions

Reduced ALFF in the OFC suggests hypo-functioning of emotion regulation in the affective network. Enhanced anti-correlation of activity between the amygdala and OFC may reflect dysfunction of the amygdala-OFC network and additionally represent a pathological process of MDD.     

The Effect of Souvenaid on Functional Brain Network Organisation in Patients with Mild Alzheimer’s Disease: A Randomised Controlled Study

Background

Synaptic loss is a major hallmark of Alzheimer’s disease (AD). Disturbed organisation of large-scale functional brain networks in AD might reflect synaptic loss and disrupted neuronal communication. The medical food Souvenaid, containing the specific nutrient combination Fortasyn Connect, is designed to enhance synapse formation and function and has been shown to improve memory performance in patients with mild AD in two randomised controlled trials.

Objective

To explore the effect of Souvenaid compared to control product on brain activity-based networks, as a derivative of underlying synaptic function, in patients with mild AD.

Design

A 24-week randomised, controlled, double-blind, parallel-group, multi-country study.

Participants

179 drug-naïve mild AD patients who participated in the Souvenir II study.

Intervention

Patients were randomised 1∶1 to receive Souvenaid or an iso-caloric control product once daily for 24 weeks.

Outcome

In a secondary analysis of the Souvenir II study, electroencephalography (EEG) brain networks were constructed and graph theory was used to quantify complex brain structure. Local brain network connectivity (normalised clustering coefficient gamma) and global network integration (normalised characteristic path length lambda) were compared between study groups, and related to memory performance.

Results

The network measures in the beta band were significantly different between groups: they decreased in the control group, but remained relatively unchanged in the active group. No consistent relationship was found between these network measures and memory performance.

Conclusions

The current results suggest that Souvenaid preserves the organisation of brain networks in patients with mild AD within 24 weeks, hypothetically counteracting the progressive network disruption over time in AD. The results strengthen the hypothesis that Souvenaid affects synaptic integrity and function. Secondly, we conclude that advanced EEG analysis, using the mathematical framework of graph theory, is useful and feasible for assessing the effects of interventions.

Trial registration

Dutch Trial Register NTR1975.     

SAGE: String-overlap Assembly of GEnomes

Background

De novo genome assembly of next-generation sequencing data is one of the most important current problems in bioinformatics, essential in many biological applications. In spite of significant amount of work in this area, better solutions are still very much needed.

Results

We present a new program, SAGE, for de novo genome assembly. As opposed to most assemblers, which are de Bruijn graph based, SAGE uses the string-overlap graph. SAGE builds upon great existing work on string-overlap graph and maximum likelihood assembly, bringing an important number of new ideas, such as the efficient computation of the transitive reduction of the string overlap graph, the use of (generalized) edge multiplicity statistics for more accurate estimation of read copy counts, and the improved use of mate pairs and min-cost flow for supporting edge merging. The assemblies produced by SAGE for several short and medium-size genomes compared favourably with those of existing leading assemblers.

Conclusions

SAGE benefits from innovations in almost every aspect of the assembly process: error correction of input reads, string-overlap graph construction, read copy counts estimation, overlap graph analysis and reduction, contig extraction, and scaffolding. We hope that these new ideas will help advance the current state-of-the-art in an essential area of research in genomics.

Electronic supplementary material

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

Hierarchical Alteration of Brain Structural and Functional Networks in Female Migraine Sufferers

Background

Little is known about the changes of brain structural and functional connectivity networks underlying the pathophysiology in migraine. We aimed to investigate how the cortical network reorganization is altered by frequent cortical overstimulation associated with migraine.

Methodology/Principal Findings

Gray matter volumes and resting-state functional magnetic resonance imaging signal correlations were employed to construct structural and functional networks between brain regions in 43 female patients with migraine (PM) and 43 gender-matched healthy controls (HC) by using graph theory-based approaches. Compared with the HC group, the patients showed abnormal global topology in both structural and functional networks, characterized by higher mean clustering coefficients without significant change in the shortest absolute path length, which indicated that the PM lost optimal topological organization in their cortical networks. Brain hubs related to pain-processing revealed abnormal nodal centrality in both structural and functional networks, including the precentral gyrus, orbital part of the inferior frontal gyrus, parahippocampal gyrus, anterior cingulate gyrus, thalamus, temporal pole of the middle temporal gyrus and the inferior parietal gyrus. Negative correlations were found between migraine duration and regions with abnormal centrality. Furthermore, the dysfunctional connections in patients'' cortical networks formed into a connected component and three dysregulated modules were identified involving pain-related information processing and motion-processing visual networks.

Conclusions

Our results may reflect brain alteration dynamics resulting from migraine and suggest that long-term and high-frequency headache attacks may cause both structural and functional connectivity network reorganization. The disrupted information exchange between brain areas in migraine may be reshaped into a hierarchical modular structure progressively.     

Innate synchronous oscillations in freely-organized small neuronal circuits

Background

Information processing in neuronal networks relies on the network''s ability to generate temporal patterns of action potentials. Although the nature of neuronal network activity has been intensively investigated in the past several decades at the individual neuron level, the underlying principles of the collective network activity, such as the synchronization and coordination between neurons, are largely unknown. Here we focus on isolated neuronal clusters in culture and address the following simple, yet fundamental questions: What is the minimal number of cells needed to exhibit collective dynamics? What are the internal temporal characteristics of such dynamics and how do the temporal features of network activity alternate upon crossover from minimal networks to large networks?

Methodology/Principal Findings

We used network engineering techniques to induce self-organization of cultured networks into neuronal clusters of different sizes. We found that small clusters made of as few as 40 cells already exhibit spontaneous collective events characterized by innate synchronous network oscillations in the range of 25 to 100 Hz. The oscillation frequency of each network appeared to be independent of cluster size. The duration and rate of the network events scale with cluster size but converge to that of large uniform networks. Finally, the investigation of two coupled clusters revealed clear activity propagation with master/slave asymmetry.

Conclusions/Significance

The nature of the activity patterns observed in small networks, namely the consistent emergence of similar activity across networks of different size and morphology, suggests that neuronal clusters self-regulate their activity to sustain network bursts with internal oscillatory features. We therefore suggest that clusters of as few as tens of cells can serve as a minimal but sufficient functional network, capable of sustaining oscillatory activity. Interestingly, the frequencies of these oscillations are similar those observed in vivo.     

Loss of 'small-world' networks in Alzheimer's disease: graph analysis of FMRI resting-state functional connectivity

Background

Local network connectivity disruptions in Alzheimer''s disease patients have been found using graph analysis in BOLD fMRI. Other studies using MEG and cortical thickness measures, however, show more global long distance connectivity changes, both in functional and structural imaging data. The form and role of functional connectivity changes thus remains ambiguous. The current study shows more conclusive data on connectivity changes in early AD using graph analysis on resting-state condition fMRI data.

Methodology/Principal Findings

18 mild AD patients and 21 healthy age-matched control subjects without memory complaints were investigated in resting-state condition with MRI at 1.5 Tesla. Functional coupling between brain regions was calculated on the basis of pair-wise synchronizations between regional time-series. Local (cluster coefficient) and global (path length) network measures were quantitatively defined. Compared to controls, the characteristic path length of AD functional networks is closer to the theoretical values of random networks, while no significant differences were found in cluster coefficient. The whole-brain average synchronization does not differ between Alzheimer and healthy control groups. Post-hoc analysis of the regional synchronization reveals increased AD synchronization involving the frontal cortices and generalized decreases located at the parietal and occipital regions. This effectively translates in a global reduction of functional long-distance links between frontal and caudal brain regions.

Conclusions/Significance

We present evidence of AD-induced changes in global brain functional connectivity specifically affecting long-distance connectivity. This finding is highly relevant for it supports the anterior-posterior disconnection theory and its role in AD. Our results can be interpreted as reflecting the randomization of the brain functional networks in AD, further suggesting a loss of global information integration in disease.     

Identification of Direct and Indirect Social Network Effects in the Pathophysiology of Insulin Resistance in Obese Human Subjects

Objective

The aim of the present study was to examine to what extent different social network mechanisms are involved in the pathogenesis of obesity and insulin-resistance.

Design

We used nonparametric and parametric regression models to analyse whether individual BMI and HOMA-IR are determined by social network characteristics.

Subjects and Methods

A total of 677 probands (EGO) and 3033 social network partners (ALTER) were included in the study. Data gathered from the probands include anthropometric measures, HOMA-IR index, health attitudes, behavioural and socio-economic variables and social network data.

Results

We found significant treatment effects for ALTERs frequent dieting (p<0.001) and ALTERs health oriented nutritional attitudes (p<0.001) on EGO''s BMI, establishing a significant indirect network effect also on EGO''s insulin resistance. Most importantly, we also found significant direct social network effects on EGO''s insulin resistance, evidenced by an effect of ALTERs frequent dieting (p = 0.033) and ALTERs sport activities (p = 0.041) to decrease EGO''s HOMA-IR index independently of EGO''s BMI.

Conclusions

Social network phenomena appear not only to be relevant for the spread of obesity, but also for the spread of insulin resistance as the basis for type 2 diabetes. Attitudes and behaviour of peer groups influence EGO''s health status not only via social mechanisms, but also via socio-biological mechanisms, i.e. higher brain areas might be influenced not only by biological signals from the own organism, but also by behaviour and knowledge from different human individuals. Our approach allows the identification of peer group influence controlling for potential homophily even when using cross-sectional observational data.     

Do we protect or discriminate? Representation of senior adults in clinical trials

Aim

The analysis of barriers responsible for low recruitment of older patients in clinical trials and presentation of possible solutions are the subject of this review.

Background

Europe''s population is ageing, and the group of people who more frequently develop neoplasms increases. Oncologists are confronted with a new challenge – how to treat cancer in this group of patients, especially considering the lack of Evidence Based Medicine (EBM) guidelines for treatment of cancer in the elderly population.

Materials and methods

Medline search and analysis of studies published between 1999 and 2012, containing key words: senior adults, cancer, elderly in clinical trials.

Results

Detailed analysis of relevant studies demonstrated that senior adults are underrepresented in clinical trials. Moreover, there is a lack of trials exclusively designed for this heterogeneous group of patients. The analysis of reasons for low recruitment of older patients in clinical trials revealed barriers dependent on patient''s and physician''s attitudes as well as institutional and logistic problems.

Conclusions

It is necessary to widen the scale of trials of all phases in the group of seniors with appropriate assessment of toxicity. This will allow a proper stratification and obtaining representative groups for statistical analysis and credible trial results. Another priority is the design of trials dedicated exclusively to the elderly.     

Exact reconstruction of gene regulatory networks using compressive sensing

Background

We consider the problem of reconstructing a gene regulatory network structure from limited time series gene expression data, without any a priori knowledge of connectivity. We assume that the network is sparse, meaning the connectivity among genes is much less than full connectivity. We develop a method for network reconstruction based on compressive sensing, which takes advantage of the network’s sparseness.

Results

For the case in which all genes are accessible for measurement, and there is no measurement noise, we show that our method can be used to exactly reconstruct the network. For the more general problem, in which hidden genes exist and all measurements are contaminated by noise, we show that our method leads to reliable reconstruction. In both cases, coherence of the model is used to assess the ability to reconstruct the network and to design new experiments. We demonstrate that it is possible to use the coherence distribution to guide biological experiment design effectively. By collecting a more informative dataset, the proposed method helps reduce the cost of experiments. For each problem, a set of numerical examples is presented.

Conclusions

The method provides a guarantee on how well the inferred graph structure represents the underlying system, reveals deficiencies in the data and model, and suggests experimental directions to remedy the deficiencies.

Electronic supplementary material

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

Functional brain network modularity captures inter- and intra-individual variation in working memory capacity

Background

Cognitive abilities, such as working memory, differ among people; however, individuals also vary in their own day-to-day cognitive performance. One potential source of cognitive variability may be fluctuations in the functional organization of neural systems. The degree to which the organization of these functional networks is optimized may relate to the effective cognitive functioning of the individual. Here we specifically examine how changes in the organization of large-scale networks measured via resting state functional connectivity MRI and graph theory track changes in working memory capacity.

Methodology/Principal Findings

Twenty-two participants performed a test of working memory capacity and then underwent resting-state fMRI. Seventeen subjects repeated the protocol three weeks later. We applied graph theoretic techniques to measure network organization on 34 brain regions of interest (ROI). Network modularity, which measures the level of integration and segregation across sub-networks, and small-worldness, which measures global network connection efficiency, both predicted individual differences in memory capacity; however, only modularity predicted intra-individual variation across the two sessions. Partial correlations controlling for the component of working memory that was stable across sessions revealed that modularity was almost entirely associated with the variability of working memory at each session. Analyses of specific sub-networks and individual circuits were unable to consistently account for working memory capacity variability.

Conclusions/Significance

The results suggest that the intrinsic functional organization of an a priori defined cognitive control network measured at rest provides substantial information about actual cognitive performance. The association of network modularity to the variability in an individual''s working memory capacity suggests that the organization of this network into high connectivity within modules and sparse connections between modules may reflect effective signaling across brain regions, perhaps through the modulation of signal or the suppression of the propagation of noise.     

An approach to multiscale modelling with graph grammars

Background and Aims

Functional–structural plant models (FSPMs) simulate biological processes at different spatial scales. Methods exist for multiscale data representation and modification, but the advantages of using multiple scales in the dynamic aspects of FSPMs remain unclear. Results from multiscale models in various other areas of science that share fundamental modelling issues with FSPMs suggest that potential advantages do exist, and this study therefore aims to introduce an approach to multiscale modelling in FSPMs.

Methods

A three-part graph data structure and grammar is revisited, and presented with a conceptual framework for multiscale modelling. The framework is used for identifying roles, categorizing and describing scale-to-scale interactions, thus allowing alternative approaches to model development as opposed to correlation-based modelling at a single scale. Reverse information flow (from macro- to micro-scale) is catered for in the framework. The methods are implemented within the programming language XL.

Key Results

Three example models are implemented using the proposed multiscale graph model and framework. The first illustrates the fundamental usage of the graph data structure and grammar, the second uses probabilistic modelling for organs at the fine scale in order to derive crown growth, and the third combines multiscale plant topology with ozone trends and metabolic network simulations in order to model juvenile beech stands under exposure to a toxic trace gas.

Conclusions

The graph data structure supports data representation and grammar operations at multiple scales. The results demonstrate that multiscale modelling is a viable method in FSPM and an alternative to correlation-based modelling. Advantages and disadvantages of multiscale modelling are illustrated by comparisons with single-scale implementations, leading to motivations for further research in sensitivity analysis and run-time efficiency for these models.     

An algorithm for efficient constrained mate selection

Background

Mate selection can be used as a framework to balance key technical, cost and logistical issues while implementing a breeding program at a tactical level. The resulting mating lists accommodate optimal contributions of parents to future generations, in conjunction with other factors such as progeny inbreeding, connection between herds, use of reproductive technologies, management of the genetic distribution of nominated traits, and management of allele/genotype frequencies for nominated QTL/markers.

Methods

This paper describes a mate selection algorithm that is widely used and presents an extension that makes it possible to apply constraints on certain matings, as dictated through a group mating permission matrix.

Results

This full algorithm leads to simpler applications, and to computing speed for the scenario tested, which is several hundred times faster than the previous strategy of penalising solutions that break constraints.

Conclusions

The much higher speed of the method presented here extends the use of mate selection and enables implementation in relatively large programs across breeding units.