Bifurcations in adaptive vascular networks: Toward model calibration.

Transport networks are crucial for the functioning of natural and technological systems. We study a mathematical model of vascular network adaptation, where the network structure dynamically adjusts to changes in blood flow and pressure. The model is based on local feedback mechanisms that occur on different time scales in the mammalian vasculature. The cost exponent γ tunes the vessel growth in the adaptation rule, and we test the hypothesis that the cost exponent is γ=1/2 for vascular systems [D. Hu and D. Cai, Phys. Rev. Lett. 111, 138701 (2013)]. We first perform bifurcation analysis for a simple triangular network motif with a fluctuating demand and then conduct numerical simulations on network topologies extracted from perivascular networks of rodent brains. We compare the model predictions with experimental data and find that γ is closer to 1 than to 1/2 for the model to be consistent with the data. Our study, thus, aims at addressing two questions: (i) Is a specific measured flow network consistent in terms of physical reality? (ii) Is the adaptive dynamic model consistent with measured network data? We conclude that the model can capture some aspects of vascular network formation and adaptation, but also suggest some limitations and directions for future research. Our findings contribute to a general understanding of the dynamics in adaptive transport networks, which is essential for studying mammalian vasculature and developing self-organizing piping systems.

Patterning the insect eye: From stochastic to deterministic mechanisms.

While most processes in biology are highly deterministic, stochastic mechanisms are sometimes used to increase cellular diversity. In human and Drosophila eyes, photoreceptors sensitive to different wavelengths of light are distributed in stochastic patterns, and one such patterning system has been analyzed in detail in the Drosophila retina. Interestingly, some species in the dipteran family Dolichopodidae (the "long legged" flies, or "Doli") instead exhibit highly orderly deterministic eye patterns. In these species, alternating columns of ommatidia (unit eyes) produce corneal lenses of different colors. Occasional perturbations in some individuals disrupt the regular columns in a way that suggests that patterning occurs via a posterior-to-anterior signaling relay during development, and that specification follows a local, cellular-automaton-like rule. We hypothesize that the regulatory mechanisms that pattern the eye are largely conserved among flies and that the difference between unordered Drosophila and ordered dolichopodid eyes can be explained in terms of relative strengths of signaling interactions rather than a rewiring of the regulatory network itself. We present a simple stochastic model that is capable of explaining both the stochastic Drosophila eye and the striped pattern of Dolichopodidae eyes and thereby characterize the least number of underlying developmental rules necessary to produce both stochastic and deterministic patterns. We show that only small changes to model parameters are needed to also reproduce intermediate, semi-random patterns observed in another Doli species, and quantification of ommatidial distributions in these eyes suggests that their patterning follows similar rules.

Cover-Encodings of Fitness Landscapes.

The traditional way of tackling discrete optimization problems is by using local search on suitably defined cost or fitness landscapes. Such approaches are however limited by the slowing down that occurs when the local minima that are a feature of the typically rugged landscapes encountered arrest the progress of the search process. Another way of tackling optimization problems is by the use of heuristic approximations to estimate a global cost minimum. Here, we present a combination of these two approaches by using cover-encoding maps which map processes from a larger search space to subsets of the original search space. The key idea is to construct cover-encoding maps with the help of suitable heuristics that single out near-optimal solutions and result in landscapes on the larger search space that no longer exhibit trapping local minima. We present cover-encoding maps for the problems of the traveling salesman, number partitioning, maximum matching and maximum clique; the practical feasibility of our method is demonstrated by simulations of adaptive walks on the corresponding encoded landscapes which find the global minima for these problems.

Temporal networks: slowing down diffusion by long lasting interactions.

Interactions among units in complex systems occur in a specific sequential order, thus affecting the flow of information, the propagation of diseases, and general dynamical processes. We investigate the Laplacian spectrum of temporal networks and compare it with that of the corresponding aggregate network. First, we show that the spectrum of the ensemble average of a temporal network has identical eigenmodes but smaller eigenvalues than the aggregate networks. In large networks without edge condensation, the expected temporal dynamics is a time-rescaled version of the aggregate dynamics. Even for single sequential realizations, diffusive dynamics is slower in temporal networks. These discrepancies are due to the noncommutability of interactions. We illustrate our analytical findings using a simple temporal motif, larger network models, and real temporal networks.

Order-disorder transition in the zero-temperature Ising model on random graphs.

The zero-temperature Ising model is known to reach a fully ordered ground state in sufficiently dense random graphs. In sparse random graphs, the dynamics gets absorbed in disordered local minima at magnetization close to zero. Here, we find that the nonequilibrium transition between the ordered and the disordered regime occurs at an average degree that slowly grows with the graph size. The system shows bistability: The distribution of the absolute magnetization in the reached absorbing state is bimodal, with peaks only at zero and unity. For a fixed system size, the average time to absorption behaves nonmonotonically as a function of average degree. The peak value of the average absorption time grows as a power law of the system size. These findings have relevance for community detection, opinion dynamics, and games on networks.

Stability of Boolean and continuous dynamics.

Regulatory dynamics in biology is often described by continuous rate equations for continuously varying chemical concentrations. Binary discretization of state space and time leads to Boolean dynamics. In the latter, the dynamics has been called unstable if flip perturbations lead to damage spreading. Here, we find that this stability classification strongly differs from the stability properties of the original continuous dynamics under small perturbations of the state vector. In particular, random networks of nodes with large sensitivity yield stable dynamics under small perturbations.

FRANz: reconstruction of wild multi-generation pedigrees.

SUMMARY: We present a software package for pedigree reconstruction in natural populations using co-dominant genomic markers such as microsatellites and single nucleotide polymorphisms (SNPs). If available, the algorithm makes use of prior information such as known relationships (sub-pedigrees) or the age and sex of individuals. Statistical confidence is estimated by Markov Chain Monte Carlo (MCMC) sampling. The accuracy of the algorithm is demonstrated for simulated data as well as an empirical dataset with known pedigree. The parentage inference is robust even in the presence of genotyping errors. AVAILABILITY: The C source code of FRANz can be obtained under the GPL from http://www.bioinf.uni-leipzig.de/Software/FRANz/.

Reconstruction of pedigrees in clonal plant populations.

We present a Bayesian method for the reconstruction of pedigrees in clonal populations using co-dominant genomic markers such as microsatellites and single nucleotide polymorphisms (SNPs). The accuracy of the algorithm is demonstrated for simulated data. We show that the joint estimation of parameters of interest such as the rate of self-fertilization is possible with high accuracy even with marker panels of moderate power. Classical methods can only assign a very limited number of statistically significant parentages in this case and would therefore fail. Statistical confidence is estimated by Markov Chain Monte Carlo (MCMC) sampling. The method is implemented in a fast and easy to use open source software that scales to large datasets with many thousand individuals.

Statistics of cycles in large networks.

The occurrence of self-avoiding closed paths (cycles) in networks is studied under varying rules of wiring. As a main result, we find that the dependence between network size and typical cycle length is algebraic, (h) proportional to Nalpha, with distinct values of for different wiring rules. The Barabasi-Albert model has alpha=1. Different preferential and nonpreferential attachment rules and the growing Internet graph yield alpha<1. Computation of the statistics of cycles at arbitrary length is made possible by the introduction of an efficient sampling algorithm.

Competition in the presence of aging: dominance, coexistence, and alternation between states.

We study the stochastic dynamics of coupled states with transition probabilities depending on local persistence, this is, the time since a state has changed. When the system has a preference to adopt older states the system orders quickly due to the dominance of old states. When preference for new states prevails, the system can show coexistence of states or synchronized collective behavior resulting in long ordering times. In this case, the magnetization of the system oscillates around zero. Finally we discuss a potential application in social systems.

Stable and unstable attractors in Boolean networks.

Boolean networks at the critical point have been a matter of debate for many years as, e.g., the scaling of numbers of attractors with system size. Recently it was found that this number scales superpolynomially with system size, contrary to a common earlier expectation of sublinear scaling. We point out here that these results are obtained using deterministic parallel update, where a large fraction of attractors are an artifact of the updating scheme. This limits the significance of these results for biological systems where noise is omnipresent. Here we take a fresh look at attractors in Boolean networks with the original motivation of simplified models for biological systems in mind. We test the stability of attractors with respect to infinitesimal deviations from synchronous update and find that most attractors are artifacts arising from synchronous clocking. The remaining fraction of attractors are stable against fluctuating delays. The average number of these stable attractors grows sublinearly with system size in the numerically tractable range.

Anomalous scaling in an age-dependent branching model.

We introduce a one-parametric family of tree growth models, in which branching probabilities decrease with branch age τ as τ(-α). Depending on the exponent α, the scaling of tree depth with tree size n displays a transition between the logarithmic scaling of random trees and an algebraic growth. At the transition (α=1) tree depth grows as (logn)(2). This anomalous scaling is in good agreement with the trend observed in evolution of biological species, thus providing a theoretical support for age-dependent speciation and associating it to the occurrence of a critical point.

Growing scale-free networks with small-world behavior.

In the context of growing networks, we introduce a simple dynamical model that unifies the generic features of real networks: scale-free distribution of degree and the small-world effect. While the average shortest path length increases logarithmically as in random networks, the clustering coefficient assumes a large value independent of system size. We derive analytical expressions for the clustering coefficient in two limiting cases: random [C approximately (ln N)(2)/N] and highly clustered (C=5/6) scale-free networks.

Highly clustered scale-free networks.

We propose a model for growing networks based on a finite memory of the nodes. The model shows stylized features of real-world networks: power-law distribution of degree, linear preferential attachment of new links, and a negative correlation between the age of a node and its link attachment rate. Notably, the degree distribution is conserved even though only the most recently grown part of the network is considered. As the network grows, the clustering reaches an asymptotic value larger than that for regular lattices of the same average connectivity and similar to the one observed in the networks of movie actors, coauthorship in science, and word synonyms. These highly clustered scale-free networks indicate that memory effects are crucial for a correct description of the dynamics of growing networks.

Nonequilibrium transitions in complex networks: a model of social interaction.

We analyze the nonequilibrium order-disorder transition of Axelrod's model of social interaction in several complex networks. In a small-world network, we find a transition between an ordered homogeneous state and a disordered state. The transition point is shifted by the degree of spatial disorder of the underlying network, the network disorder favoring ordered configurations. In random scale-free networks the transition is only observed for finite size systems, showing system size scaling, while in the thermodynamic limit only ordered configurations are always obtained. Thus, in the thermodynamic limit the transition disappears. However, in structured scale-free networks, the phase transition between an ordered and a disordered phase is restored.

Effective dimensions and percolation in hierarchically structured scale-free networks.

We introduce appropriate definitions of dimensions in order to characterize the fractal properties of complex networks. We compute these dimensions in a hierarchically structured network of particular interest. In spite of the nontrivial character of this network that displays scale-free connectivity among other features, it turns out to be approximately one dimensional. The dimensional characterization is in agreement with the results on statistics of site percolation and other dynamical processes implemented on such a network.

Global culture: a noise-induced transition in finite systems.

We analyze the effect of cultural drift, modeled as noise, in Axelrod's model for the dissemination of culture. The disordered multicultural frozen configurations are found not to be stable. This general result is proven rigorously in d=1, where the dynamics is described in terms of a Lyapunov potential. In d=2, the dynamics is governed by the average relaxation time T of perturbations. Noise at a rate r or =T(-1) sustains disorder. In the thermodynamic limit, the relaxation time diverges and global polarization persists in spite of a dynamics of local convergence.

Boolean networks with veto functions.

Boolean networks are discrete dynamical systems for modeling regulation and signaling in living cells. We investigate a particular class of Boolean functions with inhibiting inputs exerting a veto (forced zero) on the output. We give analytical expressions for the sensitivity of these functions and provide evidence for their role in natural systems. In an intracellular signal transduction network [Helikar et al., Proc. Natl. Acad. Sci. USA 105, 1913 (2008)], the functions with veto are over-represented by a factor exceeding the over-representation of threshold functions and canalyzing functions in the same system. In Boolean networks for control of the yeast cell cycle [Li et al., Proc. Natl. Acad. Sci. USA 101, 4781 (2004); Davidich et al., PLoS ONE 3, e1672 (2008)], no or minimal changes to the wiring diagrams are necessary to formulate their dynamics in terms of the veto functions introduced here.

Prediction of lethal and synthetically lethal knock-outs in regulatory networks.

The complex interactions involved in regulation of a cell's function are captured by its interaction graph. More often than not, detailed knowledge about enhancing or suppressive regulatory influences and cooperative effects is lacking and merely the presence or absence of directed interactions is known. Here, we investigate to which extent such reduced information allows to forecast the effect of a knock-out or a combination of knock-outs. Specifically, we ask in how far the lethality of eliminating nodes may be predicted by their network centrality, such as degree and betweenness, without knowing the function of the system. The function is taken as the ability to reproduce a fixed point under a discrete Boolean dynamics. We investigate two types of stochastically generated networks: fully random networks and structures grown with a mechanism of node duplication and subsequent divergence of interactions. On all networks we find that the out-degree is a good predictor of the lethality of a single node knock-out. For knock-outs of node pairs, the fraction of successors shared between the two knocked-out nodes (out-overlap) is a good predictor of synthetic lethality. Out-degree and out-overlap are locally defined and computationally simple centrality measures that provide a predictive power close to the optimal predictor.

Landscape encodings enhance optimization.

Hard combinatorial optimization problems deal with the search for the minimum cost solutions (ground states) of discrete systems under strong constraints. A transformation of state variables may enhance computational tractability. It has been argued that these state encodings are to be chosen invertible to retain the original size of the state space. Here we show how redundant non-invertible encodings enhance optimization by enriching the density of low-energy states. In addition, smooth landscapes may be established on encoded state spaces to guide local search dynamics towards the ground state.