Parallel structures in multidimensional networks

What restrictions does the space dimension impose on a variety of multidimensional regular networks? The parallel representation method is used to answer this question. An analytical relation of regular network dimension with the connectivity of vertices and the perimeter of elementary contours has been established. It has also been shown that a infinite dimensional network is equivalent to an infinite tree. In addition, the problem of closed regular polytops inside networks is discussed.     

The impacts of network topology on disease spread

Individuals in a population susceptible to a disease may be represented as vertices in a network, with the edges that connect vertices representing social and/or spatial contact between individuals. Networks, which explicitly included six different patterns of connection between vertices, were created. Both scale-free networks and random graphs showed a different response in path level to increasing levels of clustering than regular lattices. Clustering promoted short path lengths in all network types, but randomly assembled networks displayed a logarithmic relationship between degree and path length; whereas this response was linear in regular lattices. In all cases, small-world models, generated by rewiring the connections of a regular lattice, displayed properties, which spanned the gap between random and regular networks.Simulation of a disease in these networks showed a strong response to connectance pattern, even when the number of edges and vertices were approximately equal. Epidemic spread was fastest, and reached the largest size, in scale-free networks, then in random graphs. Regular lattices were the slowest to be infected, and rewired lattices were intermediate between these two extremes. Scale-free networks displayed the capacity to produce an epidemic even at a likelihood of infection, which was too low to produce an epidemic for the other network types. The interaction between the statistical properties of the network and the results of epidemic spread provides a useful tool for assessing the risk of disease spread in more realistic networks.     

From heterogeneous healthcare data to disease-specific biomarker networks: A hierarchical Bayesian network approach

In this work, we introduce an entirely data-driven and automated approach to reveal disease-associated biomarker and risk factor networks from heterogeneous and high-dimensional healthcare data. Our workflow is based on Bayesian networks, which are a popular tool for analyzing the interplay of biomarkers. Usually, data require extensive manual preprocessing and dimension reduction to allow for effective learning of Bayesian networks. For heterogeneous data, this preprocessing is hard to automatize and typically requires domain-specific prior knowledge. We here combine Bayesian network learning with hierarchical variable clustering in order to detect groups of similar features and learn interactions between them entirely automated. We present an optimization algorithm for the adaptive refinement of such group Bayesian networks to account for a specific target variable, like a disease. The combination of Bayesian networks, clustering, and refinement yields low-dimensional but disease-specific interaction networks. These networks provide easily interpretable, yet accurate models of biomarker interdependencies. We test our method extensively on simulated data, as well as on data from the Study of Health in Pomerania (SHIP-TREND), and demonstrate its effectiveness using non-alcoholic fatty liver disease and hypertension as examples. We show that the group network models outperform available biomarker scores, while at the same time, they provide an easily interpretable interaction network.     

Gradient directed regularization for sparse Gaussian concentration graphs, with applications to inference of genetic networks

Large-scale microarray gene expression data provide the possibility of constructing genetic networks or biological pathways. Gaussian graphical models have been suggested to provide an effective method for constructing such genetic networks. However, most of the available methods for constructing Gaussian graphs do not account for the sparsity of the networks and are computationally more demanding or infeasible, especially in the settings of high dimension and low sample size. We introduce a threshold gradient descent (TGD) regularization procedure for estimating the sparse precision matrix in the setting of Gaussian graphical models and demonstrate its application to identifying genetic networks. Such a procedure is computationally feasible and can easily incorporate prior biological knowledge about the network structure. Simulation results indicate that the proposed method yields a better estimate of the precision matrix than the procedures that fail to account for the sparsity of the graphs. We also present the results on inference of a gene network for isoprenoid biosynthesis in Arabidopsis thaliana. These results demonstrate that the proposed procedure can indeed identify biologically meaningful genetic networks based on microarray gene expression data.     

Dimensionality of Social Networks Using Motifs and Eigenvalues

We consider the dimensionality of social networks, and develop experiments aimed at predicting that dimension. We find that a social network model with nodes and links sampled from an m-dimensional metric space with power-law distributed influence regions best fits samples from real-world networks when m scales logarithmically with the number of nodes of the network. This supports a logarithmic dimension hypothesis, and we provide evidence with two different social networks, Facebook and LinkedIn. Further, we employ two different methods for confirming the hypothesis: the first uses the distribution of motif counts, and the second exploits the eigenvalue distribution.     

Spiking regularity in a noisy small-world neuronal network

The regularity of spiking oscillations is studied in the networks with different topological structures. The network is composed of coupled Fitz-Hugh-Nagumo neurons driven by colored noise. The investigation illustrates that the spike train in both the regular and the Watts-Strogatz small-world neuronal networks can show the best regularity at a moderate noise intensity, indicating the existence of coherence resonance. Moreover, the temporal coherence of the spike train in the small-world network is superior to that in a regular network due to the increase of the randomness of the network topology. Besides the noise intensity, the spiking regularity can be optimized by tuning the randomness of the network topological structure or by tuning the correlation time of the colored noise. In particular, under the cooperation of the small-world topology and the correlation time, the spike train with good regularity could sustain a large magnitude of the local noise.     

A Full Bayesian Approach for Boolean Genetic Network Inference

Boolean networks are a simple but efficient model for describing gene regulatory systems. A number of algorithms have been proposed to infer Boolean networks. However, these methods do not take full consideration of the effects of noise and model uncertainty. In this paper, we propose a full Bayesian approach to infer Boolean genetic networks. Markov chain Monte Carlo algorithms are used to obtain the posterior samples of both the network structure and the related parameters. In addition to regular link addition and removal moves, which can guarantee the irreducibility of the Markov chain for traversing the whole network space, carefully constructed mixture proposals are used to improve the Markov chain Monte Carlo convergence. Both simulations and a real application on cell-cycle data show that our method is more powerful than existing methods for the inference of both the topology and logic relations of the Boolean network from observed data.     

The effect of negative feedback loops on the dynamics of boolean networks

Feedback loops play an important role in determining the dynamics of biological networks. To study the role of negative feedback loops, this article introduces the notion of distance-to-positive-feedback which, in essence, captures the number of independent negative feedback loops in the network, a property inherent in the network topology. Through a computational study using Boolean networks, it is shown that distance-to-positive-feedback has a strong influence on network dynamics and correlates very well with the number and length of limit cycles in the phase space of the network. To be precise, it is shown that, as the number of independent negative feedback loops increases, the number (length) of limit cycles tends to decrease (increase). These conclusions are consistent with the fact that certain natural biological networks exhibit generally regular behavior and have fewer negative feedback loops than randomized networks with the same number of nodes and same connectivity.     

Inferring gene regulatory networks using differential evolution with local search heuristics

We present a memetic algorithm for evolving the structure of biomolecular interactions and inferring the effective kinetic parameters from the time series data of gene expression using the decoupled Ssystem formalism. We propose an Information Criteria based fitness evaluation for gene network model selection instead of the conventional Mean Squared Error (MSE) based fitness evaluation. A hill-climbing local-search method has been incorporated in our evolutionary algorithm for efficiently attaining the skeletal architecture which is most frequently observed in biological networks. The suitability of the method is tested in gene circuit reconstruction experiments, varying the network dimension and/or characteristics, the amount of gene expression data used for inference and the noise level present in expression profiles. The reconstruction method inferred the network topology and the regulatory parameters with high accuracy. Nevertheless, the performance is limited to the amount of expression data used and the noise level present in the data. The proposed fitness function has been found more suitable for identifying correct network topology and for estimating the accurate parameter values compared to the existing ones. Finally, we applied the methodology for analyzing the cell-cycle gene expression data of budding yeast and reconstructed the network of some key regulators.     

Comparison of Tree-Child Phylogenetic Networks

Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a well-founded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called tree-child phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the well-known Robinson-Foulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. Simple polynomial algorithms for reconstructing a tree-child phylogenetic network from its path multiplicity vectors, for computing the distance between two tree-child phylogenetic networks and for aligning a pair of tree-child phylogenetic networks, are provided. They have been implemented as a Perl package and a Java applet, which can be found at http://bioinfo.uib.es/~recerca/phylonetworks/mudistance/.     

Kernel-Kohonen networks

We investigate the combination of the Kohonen networks with the kernel methods in the context of classification. We use the idea of kernel functions to handle products of vectors of arbitrary dimension. We indicate how to build Kohonen networks with robust classification performance by transformation of the original data vectors into a possibly infinite dimensional space. The resulting Kohonen networks preserve a non-Euclidean neighborhood structure of the input space that fits the properties of the data. We show how to optimize the transformation of the data vectors in order to obtain higher classification performance. We compare the kernel-Kohonen networks with the regular Kohonen networks in the context of a classification task.     

Organized packaging of kinetoplast DNA networks

The kinetoplast DNA (kDNA) of Trypanosoma equiperdum is organized as a complex structure of catenated circular DNA molecules. The major component of the kDNA network is the one kilobase minicircle that is present at about 10,000 copies per network. We have developed two assays to examine the structure of kDNA networks compacted in vitro with spermidine. Our results suggest that minicircles are arranged into a regular structure with an exposed domain which is DNAase I- and restriction-sensitive and a protected domain which is resistant to restriction endonucleases and DNAase I. This regularly packaged structure is dependent upon spermidine compaction and the circularity of the kDNA, but does not require supercoiled minicircles or catenated networks.     

The small world inside large metabolic networks

The metabolic network of the catabolic, energy and biosynthetic metabolism of Escherichia coli is a paradigmatic case for the large genetic and metabolic networks that functional genomics efforts are beginning to elucidate. To analyse the structure of previously unknown networks involving hundreds or thousands of components by simple visual inspection is impossible, and quantitative approaches are needed to analyse them. We have undertaken a graph theoretical analysis of the E. coli metabolic network and find that this network is a small-world graph, a type of graph distinct from both regular and random networks and observed in a variety of seemingly unrelated areas, such as friendship networks in sociology, the structure of electrical power grids, and the nervous system of Caenorhabditis elegans. Moreover, the connectivity of the metabolites follows a power law, another unusual but by no means rare statistical distribution. This provides an objective criterion for the centrality of the tricarboxylic acid cycle to metabolism. The small-world architecture may serve to minimize transition times between metabolic states, and contains evidence about the evolutionary history of metabolism.     

Community Structure and Multi-Modal Oscillations in Complex Networks

In many types of network, the relationship between structure and function is of great significance. We are particularly interested in community structures, which arise in a wide variety of domains. We apply a simple oscillator model to networks with community structures and show that waves of regular oscillation are caused by synchronised clusters of nodes. Moreover, we show that such global oscillations may arise as a direct result of network topology. We also observe that additional modes of oscillation (as detected through frequency analysis) occur in networks with additional levels of topological hierarchy and that such modes may be directly related to network structure. We apply the method in two specific domains (metabolic networks and metropolitan transport) demonstrating the robustness of our results when applied to real world systems. We conclude that (where the distribution of oscillator frequencies and the interactions between them are known to be unimodal) our observations may be applicable to the detection of underlying community structure in networks, shedding further light on the general relationship between structure and function in complex systems.     

Wave speed in excitable random networks with spatially constrained connections

Very fast oscillations (VFO) in neocortex are widely observed before epileptic seizures, and there is growing evidence that they are caused by networks of pyramidal neurons connected by gap junctions between their axons. We are motivated by the spatio-temporal waves of activity recorded using electrocorticography (ECoG), and study the speed of activity propagation through a network of neurons axonally coupled by gap junctions. We simulate wave propagation by excitable cellular automata (CA) on random (Erdös-Rényi) networks of special type, with spatially constrained connections. From the cellular automaton model, we derive a mean field theory to predict wave propagation. The governing equation resolved by the Fisher-Kolmogorov PDE fails to describe wave speed. A new (hyperbolic) PDE is suggested, which provides adequate wave speed that saturates with network degree , in agreement with intuitive expectations and CA simulations. We further show that the maximum length of connection is a much better predictor of the wave speed than the mean length. When tested in networks with various degree distributions, wave speeds are found to strongly depend on the ratio of network moments rather than on mean degree , which is explained by general network theory. The wave speeds are strikingly similar in a diverse set of networks, including regular, Poisson, exponential and power law distributions, supporting our theory for various network topologies. Our results suggest practical predictions for networks of electrically coupled neurons, and our mean field method can be readily applied for a wide class of similar problems, such as spread of epidemics through spatial networks.     

Impact of network topology on inference of synaptic connectivity from multi-neuronal spike data simulated by a large-scale cortical network model

Many mechanisms of neural processing rely critically upon the synaptic connectivity between neurons. As our ability to simultaneously record from large populations of neurons expands, the ability to infer network connectivity from this data has become a major goal of computational neuroscience. To address this issue, we employed several different methods to infer synaptic connections from simulated spike data from a realistic local cortical network model. This approach allowed us to directly compare the accuracy of different methods in predicting synaptic connectivity. We compared the performance of model-free (coherence measure and transfer entropy) and model-based (coupled escape rate model) methods of connectivity inference, applying those methods to the simulated spike data from the model networks with different network topologies. Our results indicate that the accuracy of the inferred connectivity was higher for highly clustered, near regular, or small-world networks, while accuracy was lower for random networks, irrespective of which analysis method was employed. Among the employed methods, the model-based method performed best. This model performed with higher accuracy, was less sensitive to threshold changes, and required less data to make an accurate assessment of connectivity. Given that cortical connectivity tends to be highly clustered, our results outline a powerful analytical tool for inferring local synaptic connectivity from observations of spontaneous activity.     

Recurrence Network Analysis of the Synchronous EEG Time Series in Normal and Epileptic Brains

We sought to analyze the dynamic properties of brain electrical activity from healthy volunteers and epilepsy patients using recurrence networks. Phase-space trajectories of synchronous electroencephalogram signals were obtained through embedding dimension in phase-space reconstruction based on the distance set of space points. The recurrence matrix calculated from phase-space trajectories was identified with the adjacency matrix of a complex network. Then, we applied measures to characterize the complex network to this recurrence network. A detailed analysis revealed the following: (1) The recurrence networks of normal brains exhibited a sparser connectivity and smaller clustering coefficient compared with that of epileptic brains; (2) the small-world property existed in both normal and epileptic brains consistent with the previous empirical studies of structural and functional brain networks; and (3) the assortative property of the recurrence network was found by computing the assortative coefficients; their values increased from normal to epileptic brain which accurately suggested the difference of the states. These universal and non-universal characteristics of recurrence networks might help clearly understand the underlying neurodynamics of the brain and provide an efficient tool for clinical diagnosis.     

Using historical data for bioprocess optimization: modeling wine characteristics using artificial neural networks and archived process information

Optimization of fermentation processes is a difficult task that relies on an understanding of the complex effects of processing inputs on productivity and quality outputs. Because of the complexity of these biological systems, traditional optimization methods utilizing mathematical models and statistically designed experiments are less effective, especially on a production scale. At the same time, information is being collected on a regular basis during the course of normal manufacturing and process development that is rarely fully utilized. We are developing an optimization method in which historical process data is used to train an artificial neural network for correlation of processing inputs and outputs. Subsequently, an optimization routine is used in conjunction with the trained neural network to find optimal processing conditions given the desired product characteristics and any constraints on inputs. Wine processing is being used as a case study for this work. Using data from wine produced in our pilot winery over the past 3 years, we have demonstrated that trained neural networks can be used successfully to predict the yeast-fermentation kinetics, as well as chemical and sensory properties of the finished wine, based solely on the properties of the grapes and the intended processing. To accomplish this, a hybrid neural network training method, Stop Training with Validation (STV), has been developed to find the most desirable neural network architecture and training level. As industrial historical data will not be evenly spaced over the entire possible search space, we have also investigated the ability of the trained neural networks to interpolate and extrapolate with data not used during training. Because a company will utilize its own existing process data for this method, the result of this work will be a general fermentation optimization method that can be applied to fermentation processes to improve quality and productivity.     

基于小波和BP网络的视觉诱发电位分类识别

提出了小波分解与BP网络相结合的方法来识别视觉诱发电位（Visual Evoked Potential,VEP）。先用小波分解对VEP进行特征提取和降维。然后用BP网络进行分类识别。     

RINQ: Reference-based Indexing for Network Queries

We consider the problem of similarity queries in biological network databases. Given a database of networks, similarity query returns all the database networks whose similarity (i.e. alignment score) to a given query network is at least a specified similarity cutoff value. Alignment of two networks is a very costly operation, which makes exhaustive comparison of all the database networks with a query impractical. To tackle this problem, we develop a novel indexing method, named RINQ (Reference-based Indexing for Biological Network Queries). Our method uses a set of reference networks to eliminate a large portion of the database quickly for each query. A reference network is a small biological network. We precompute and store the alignments of all the references with all the database networks. When our database is queried, we align the query network with all the reference networks. Using these alignments, we calculate a lower bound and an approximate upper bound to the alignment score of each database network with the query network. With the help of upper and lower bounds, we eliminate the majority of the database networks without aligning them to the query network. We also quickly identify a small portion of these as guaranteed to be similar to the query. We perform pairwise alignment only for the remaining networks. We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks. Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.