Concept: Planar graph
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.
- 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.
- Journal of bioinformatics and computational biology
- Published almost 8 years ago
Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any five-point metric can be represented approximately by a planar boundary-labeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundary-labeled networks for any number of taxa.
- IEEE transactions on image processing : a publication of the IEEE Signal Processing Society
- Published over 7 years ago
A key issue in face recognition is to seek an effective descriptor for representing face appearance. In the context of considering the face image as a set of small facial regions, this paper presents a new face representation approach coined spatial feature interdependence matrix (SFIM). Unlike classical face descriptors which usually use a hierarchically organized or a sequentially concatenated structure to describe the spatial layout features extracted from local regions, SFIM is dedicated to the exploitation of the underlying feature interdependences regarding local region pairs inside a class specific face. According to SFIM, the face image is projected onto an undirected connected graph in a manner which explicitly encodes feature interdependence based relationships between local regions. We calculate the pair-wise interdependence strength as the weighted discrepancy between two feature sets extracted in a hybrid feature space fusing histograms of intensity, local binary pattern (LBP) and oriented gradients. To achieve face recognition goal, our SFIM based face descriptor is embedded in three different recognition frameworks, namely nearest neighbor search, subspace based classification and linear optimization based classification. Extensive experimental results on four well-known face databases and comprehensive comparisons with the state of the art results are provided to demonstrate the efficacy of the proposed SFIM based descriptor.
The brain is a large-scale complex network often referred to as the “connectome”. Exploring the dynamic behavior of the connectome is a challenging issue as both excellent time and space resolution is required. In this context Magneto/Electroencephalography (M/EEG) are effective neuroimaging techniques allowing for analysis of the dynamics of functional brain networks at scalp level and/or at reconstructed sources. However, a tool that can cover all the processing steps of identifying brain networks from M/EEG data is still missing. In this paper, we report a novel software package, called EEGNET, running under MATLAB (Math works, inc), and allowing for analysis and visualization of functional brain networks from M/EEG recordings. EEGNET is developed to analyze networks either at the level of scalp electrodes or at the level of reconstructed cortical sources. It includes i) Basic steps in preprocessing M/EEG signals, ii) the solution of the inverse problem to localize / reconstruct the cortical sources, iii) the computation of functional connectivity among signals collected at surface electrodes or/and time courses of reconstructed sources and iv) the computation of the network measures based on graph theory analysis. EEGNET is the unique tool that combines the M/EEG functional connectivity analysis and the computation of network measures derived from the graph theory. The first version of EEGNET is easy to use, flexible and user friendly. EEGNET is an open source tool and can be freely downloaded from this webpage: https://sites.google.com/site/eegnetworks/.
We investigate the growth dynamics of Greater London defined by the administrative boundary of the Greater London Authority, based on the evolution of its street network during the last two centuries. This is done by employing a unique dataset, consisting of the planar graph representation of nine time slices of Greater London’s road network spanning 224 years, from 1786 to 2010. Within this time-frame, we address the concept of the metropolitan area or city in physical terms, in that urban evolution reveals observable transitions in the distribution of relevant geometrical properties. Given that London has a hard boundary enforced by its long standing green belt, we show that its street network dynamics can be described as a fractal space-filling phenomena up to a capacitated limit, whence its growth can be predicted with a striking level of accuracy. This observation is confirmed by the analytical calculation of key topological properties of the planar graph, such as the topological growth of the network and its average connectivity. This study thus represents an example of a strong violation of Gibrat’s law. In particular, we are able to show analytically how London evolves from a more loop-like structure, typical of planned cities, toward a more tree-like structure, typical of self-organized cities. These observations are relevant to the discourse on sustainable urban planning with respect to the control of urban sprawl in many large cities which have developed under the conditions of spatial constraints imposed by green belts and hard urban boundaries.
The success or failure of the street network depends on its reliability. In this article, using resilience analysis, the author studies how the shape and appearance of street networks in self-organised and top-down planned cities influences urban transport. Considering London and Beijing as proxies for self-organised and top-down planned cities, the structural properties of London and Beijing networks first are investigated based on their primal and dual representations of planar graphs. The robustness of street networks then is evaluated in primal space and dual space by deactivating road links under random and intentional attack scenarios. The results show that the reliability of London street network differs from that of Beijing, which seems to rely more on its architecture and connectivity. It is found that top-down planned Beijing with its higher average degree in the dual space and assortativity in the primal space is more robust than self-organised London using the measures of maximum and second largest cluster size and network efficiency. The article offers an insight, from a network perspective, into the reliability of street patterns in self-organised and top-down planned city systems.
Mutualistic interactions repeatedly preserved across fragmented landscapes can scale-up to form a spatial metanetwork describing the distribution of interactions across patches. We explored the structure of a bird seed-dispersal (BSD) metanetwork in 16 Neotropical forest fragments to test whether a distinct subset of BSD-interactions may mediate landscape functional connectivity. The metanetwork is interaction-rich, modular and poorly connected, showing high beta-diversity and turnover of species and interactions. Interactions involving large-sized species were lost in fragments < 10 000 ha, indicating a strong filtering by habitat fragmentation on the functional diversity of BSD-interactions. Persistent interactions were performed by small-seeded, fast growing plant species and by generalist, small-bodied bird species able to cross the fragmented landscape. This reduced subset of interactions forms the metanetwork components persisting to defaunation and fragmentation, and may generate long-term deficits of carbon storage while delaying forest regeneration at the landscape level.
Sleep deprivation (SD) critically affects a range of cognitive and affective functions, typically assessed during task performance. Whether such impairments stem from changes to the brain’s intrinsic functional connectivity remain largely unknown. To examine this hypothesis, we applied graph theoretical analysis on resting-state fMRI data derived from 18 healthy participants, acquired during both sleep-rested and sleep-deprived states. We hypothesized that parameters indicative of graph connectivity, such as modularity, will be impaired by sleep deprivation and that these changes will correlate with behavioral outcomes elicited by sleep loss. As expected, our findings point to a profound reduction in network modularity without sleep, evident in the limbic, default-mode, salience and executive modules. These changes were further associated with behavioral impairments elicited by SD: a decrease in salience module density was associated with worse task performance, an increase in limbic module density was predictive of stronger amygdala activation in a subsequent emotional-distraction task and a shift in frontal hub lateralization (from left to right) was associated with increased negative mood. Altogether, these results portray a loss of functional segregation within the brain and a shift towards a more random-like network without sleep, already detected in the spontaneous activity of the sleep-deprived brain. Hum Brain Mapp, 2017. © 2017 Wiley Periodicals, Inc.
The developing human brain undergoes an astonishing sequence of events that continuously shape the structural and functional brain connectivity. Distinct regional variations in the timelines of maturational events (synaptogenesis and synaptic pruning) occurring at the synaptic level are reflected in brain measures at macroscopic resolution (cortical thickness and gray matter density). Interestingly, the observed brain changes coincide with cognitive milestones suggesting that the changing scaffold of brain circuits may subserve cognitive development. Recent advances in connectivity analysis propelled by graph theory have allowed, on one hand, the investigation of maturational changes in global organization of structural and functional brain networks; and on the other hand, the exploration of specific networks within the context of global brain networks. An emerging picture from several connectivity studies is a system-level rewiring that constantly refines the connectivity of the developing brain.