Currently, most paired link based scaffolding algorithms intrinsically mask the sequences between two linked contigs and bypass their direct link information embedded in the original de Bruijn assembly graph. Such disadvantage substantially complicates the scaffolding process and leads to the inability of resolving repetitive contig assembly. Here we present a novel algorithm, inGAP-sf, for effectively generating high-quality and continuous scaffolds. inGAP-sf achieves this by using a new strategy based on the combination of direct link and paired link graphs, in which direct link is used to increase graph connectivity and to decrease graph complexity and paired link is employed to supervise the traversing process on the direct link graph. Such advantage greatly facilitates the assembly of short-repeat enriched regions. Moreover, a new comprehensive decision model is developed to eliminate the noise routes accompanying with the introduced direct link. Through extensive evaluations on both simulated and real datasets, we demonstrated that inGAP-sf outperforms most of the genome scaffolding algorithms by generating more accurate and continuous assembly, especially for short repetitive regions.
BACKGROUND: Graph theory has been recently introduced to characterize complex brain networks, making it highly suitable to investigate altered connectivity in neurologic disorders. A current model proposes autism spectrum disorder (ASD) as a developmental disconnection syndrome, supported by converging evidence in both non-syndromic and syndromic ASD. However, the effects of abnormal connectivity on network properties have not been well studied, particularly in syndromic ASD. To close this gap, brain functional networks of electroencephalographic (EEG) connectivity were studied through graph measures in patients with Tuberous Sclerosis Complex (TSC), a disorder with a high prevalence of ASD, as well as in patients with non-syndromic ASD. METHODS: EEG data were collected from TSC patients with ASD (n = 14) and without ASD (n = 29), from patients with non-syndromic ASD (n = 16), and from controls (n = 46). First, EEG connectivity was characterized by the mean coherence, the ratio of inter- over intra-hemispheric coherence and the ratio of long- over short-range coherence. Next, graph measures of the functional networks were computed and a resilience analysis was conducted. To distinguish effects related to ASD from those related to TSC, a two-way analysis of covariance (ANCOVA) was applied, using age as a covariate. RESULTS: Analysis of network properties revealed differences specific to TSC and ASD, and these differences were very consistent across subgroups. In TSC, both with and without a concurrent diagnosis of ASD, mean coherence, global efficiency, and clustering coefficient were decreased and the average path length was increased. These findings indicate an altered network topology. In ASD, both with and without a concurrent diagnosis of TSC, decreased long- over short-range coherence and markedly increased network resilience were found. CONCLUSIONS: The altered network topology in TSC represents a functional correlate of structural abnormalities and may play a role in the pathogenesis of neurological deficits. The increased resilience in ASD may reflect an excessively degenerate network with local overconnection and decreased functional specialization. This joint study of TSC and ASD networks provides a unique window to common neurobiological mechanisms in autism. Please see related commentary article here http://www.biomedcentral.com/1741-7015/11/55.
Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of approaches have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.
Individual differences in brain functional networks may be related to complex personal identifiers, including health, age, and ability. Dynamic network theory has been used to identify properties of dynamic brain function from fMRI data, but the majority of analyses and findings remain at the level of the group. Here, we apply hypergraph analysis, a method from dynamic network theory, to quantify individual differences in brain functional dynamics. Using a summary metric derived from the hypergraph formalism-hypergraph cardinality-we investigate individual variations in two separate, complementary data sets. The first data set (“multi-task”) consists of 77 individuals engaging in four consecutive cognitive tasks. We observe that hypergraph cardinality exhibits variation across individuals while remaining consistent within individuals between tasks; moreover, the analysis of one of the memory tasks revealed a marginally significant correspondence between hypergraph cardinality and age. This finding motivated a similar analysis of the second data set (“age-memory”), in which 95 individuals, aged 18-75, performed a memory task with a similar structure to the multi-task memory task. With the increased age range in the age-memory data set, the correlation between hypergraph cardinality and age correspondence becomes significant. We discuss these results in the context of the well-known finding linking age with network structure, and suggest that hypergraph analysis should serve as a useful tool in furthering our understanding of the dynamic network structure of the brain.
Although previous investigations of transsexual people have focused on regional brain alterations, evaluations on a network level, especially those structural in nature, are largely missing. Therefore, we investigated the structural connectome of 23 female-to-male (FtM) and 21 male-to-female (MtF) transgender patients before hormone therapy as compared with 25 female and 25 male healthy controls. Graph theoretical analysis of whole-brain probabilistic tractography networks (adjusted for differences in intracranial volume) showed decreased hemispheric connectivity ratios of subcortical/limbic areas for both transgender groups. Subsequent analysis revealed that this finding was driven by increased interhemispheric lobar connectivity weights (LCWs) in MtF transsexuals and decreased intrahemispheric LCWs in FtM patients. This was further reflected on a regional level, where the MtF group showed mostly increased local efficiencies and FtM patients decreased values. Importantly, these parameters separated each patient group from the remaining subjects for the majority of significant findings. This work complements previously established regional alterations with important findings of structural connectivity. Specifically, our data suggest that network parameters may reflect unique characteristics of transgender patients, whereas local physiological aspects have been shown to represent the transition from the biological sex to the actual gender identity.
Systemic risk, here meant as the risk of default of a large portion of the financial system, depends on the network of financial exposures among institutions. However, there is no widely accepted methodology to determine the systemically important nodes in a network. To fill this gap, we introduce, DebtRank, a novel measure of systemic impact inspired by feedback-centrality. As an application, we analyse a new and unique dataset on the USD 1.2 trillion FED emergency loans program to global financial institutions during 2008-2010. We find that a group of 22 institutions, which received most of the funds, form a strongly connected graph where each of the nodes becomes systemically important at the peak of the crisis. Moreover, a systemic default could have been triggered even by small dispersed shocks. The results suggest that the debate on too-big-to-fail institutions should include the even more serious issue of too-central-to-fail.
Network models are routinely downscaled compared to nature in terms of numbers of nodes or edges because of a lack of computational resources, often without explicit mention of the limitations this entails. While reliable methods have long existed to adjust parameters such that the first-order statistics of network dynamics are conserved, here we show that limitations already arise if also second-order statistics are to be maintained. The temporal structure of pairwise averaged correlations in the activity of recurrent networks is determined by the effective population-level connectivity. We first show that in general the converse is also true and explicitly mention degenerate cases when this one-to-one relationship does not hold. The one-to-one correspondence between effective connectivity and the temporal structure of pairwise averaged correlations implies that network scalings should preserve the effective connectivity if pairwise averaged correlations are to be held constant. Changes in effective connectivity can even push a network from a linearly stable to an unstable, oscillatory regime and vice versa. On this basis, we derive conditions for the preservation of both mean population-averaged activities and pairwise averaged correlations under a change in numbers of neurons or synapses in the asynchronous regime typical of cortical networks. We find that mean activities and correlation structure can be maintained by an appropriate scaling of the synaptic weights, but only over a range of numbers of synapses that is limited by the variance of external inputs to the network. Our results therefore show that the reducibility of asynchronous networks is fundamentally limited.
Intransitivity is a property of connected, oriented graphs representing species interactions that may drive their coexistence even in the presence of competition, the standard example being the three species Rock-Paper-Scissors game. We consider here a generalization with four species, the minimum number of species allowing other interactions beyond the single loop (one predator, one prey). We show that, contrary to the mean field prediction, on a square lattice the model presents a transition, as the parameter setting the rate at which one species invades another changes, from a coexistence to a state in which one species gets extinct. Such a dependence on the invasion rates shows that the interaction graph structure alone is not enough to predict the outcome of such models. In addition, different invasion rates permit to tune the level of transitiveness, indicating that for the coexistence of all species to persist, there must be a minimum amount of intransitivity.
- IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM
- Published over 7 years ago
Given a multiset of colors as the query and a list-colored graph, i.e. an undirected graph with a set of colors assigned to each of its vertices, in the NP-hard list-colored graph motif problem the goal is to find the largest connected subgraph such that one can select a color from the set of colors assigned to each of its vertices to obtain a subset of the query. This problem was introduced to find functional motifs in biological networks. We present a branch-and-bound algorithm named RANGI for finding and enumerating list-colored graph motifs. As our experimental results show, RANGI’s pruning methods and heuristics make it quite fast in practice compared to the algorithms presented in the literature. We also present a parallel version of RANGI that achieves acceptable scalability.
Brain connectomics research has rapidly expanded using functional MRI (fMRI) and diffusion-weighted MRI (dwMRI). A common product of these varied analyses is a connectivity matrix (CM). A CM stores the connection strength between any two regions (“nodes”) in a brain network. This format is useful for several reasons: (1) it is highly distilled, with minimal data size and complexity, (2) graph theory can be applied to characterize the network’s topology, and (3) it retains sufficient information to capture individual differences such as age, gender, intelligence quotient (IQ), or disease state. Here we introduce the UCLA Multimodal Connectivity Database (http://umcd.humanconnectomeproject.org), an openly available website for brain network analysis and data sharing. The site is a repository for researchers to publicly share CMs derived from their data. The site also allows users to select any CM shared by another user, compute graph theoretical metrics on the site, visualize a report of results, or download the raw CM. To date, users have contributed over 2000 individual CMs, spanning different imaging modalities (fMRI, dwMRI) and disorders (Alzheimer’s, autism, Attention Deficit Hyperactive Disorder). To demonstrate the site’s functionality, whole brain functional and structural connectivity matrices are derived from 60 subjects' (ages 26-45) resting state fMRI (rs-fMRI) and dwMRI data and uploaded to the site. The site is utilized to derive graph theory global and regional measures for the rs-fMRI and dwMRI networks. Global and nodal graph theoretical measures between functional and structural networks exhibit low correspondence. This example demonstrates how this tool can enhance the comparability of brain networks from different imaging modalities and studies. The existence of this connectivity-based repository should foster broader data sharing and enable larger-scale meta-analyses comparing networks across imaging modality, age group, and disease state.