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.

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.

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.

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.

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.

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.

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.

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.

A measure of individual role in collective dynamics.

Identifying key players in collective dynamics remains a challenge in several research fields, from the efficient dissemination of ideas to drug target discovery in biomedical problems. The difficulty lies at several levels: how to single out the role of individual elements in such intermingled systems, or which is the best way to quantify their importance. Centrality measures describe a node's importance by its position in a network. The key issue obviated is that the contribution of a node to the collective behavior is not uniquely determined by the structure of the system but it is a result of the interplay between dynamics and network structure. We show that dynamical influence measures explicitly how strongly a node's dynamical state affects collective behavior. For critical spreading, dynamical influence targets nodes according to their spreading capabilities. For diffusive processes it quantifies how efficiently real systems may be controlled by manipulating a single node.

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.

Efficient exploration of discrete energy landscapes.

Many physical and chemical processes, such as folding of biopolymers, are best described as dynamics on large combinatorial energy landscapes. A concise approximate description of the dynamics is obtained by partitioning the microstates of the landscape into macrostates. Since most landscapes of interest are not tractable analytically, the probabilities of transitions between macrostates need to be extracted numerically from the microscopic ones, typically by full enumeration of the state space or approximations using the Arrhenius law. Here, we propose to approximate transition probabilities by a Markov chain Monte Carlo method. For landscapes of the number partitioning problem and an RNA switch molecule, we show that the method allows for accurate probability estimates with significantly reduced computational cost.

Robustness of Boolean dynamics under knockouts.

The response to a knockout of a node is a characteristic feature of a networked dynamical system. Knockout resilience in the dynamics of the remaining nodes is a sign of robustness. Here we study the effect of knockouts for binary state sequences and their implementations in terms of Boolean threshold networks. Besides random sequences with biologically plausible constraints, we analyze the cell cycle sequence of the species Saccharomyces cerevisiae and the Boolean networks implementing it. Comparing with an appropriate null model we do not find evidence that the yeast wildtype network is optimized for high knockout resilience. Our notion of knockout resilience weakly correlates with the size of the basin of attraction, which has also been considered a measure of robustness.

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.

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/.

Universal scaling in the branching of the tree of life.

Understanding the patterns and processes of diversification of life in the planet is a key challenge of science. The Tree of Life represents such diversification processes through the evolutionary relationships among the different taxa, and can be extended down to intra-specific relationships. Here we examine the topological properties of a large set of interspecific and intraspecific phylogenies and show that the branching patterns follow allometric rules conserved across the different levels in the Tree of Life, all significantly departing from those expected from the standard null models. The finding of non-random universal patterns of phylogenetic differentiation suggests that similar evolutionary forces drive diversification across the broad range of scales, from macro-evolutionary to micro-evolutionary processes, shaping the diversity of life on the planet.

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.

Topology of biological networks and reliability of information processing.

Survival of living cells and organisms is largely based on highly reliable function of their regulatory networks. However, the elements of biological networks, e.g., regulatory genes in genetic networks or neurons in the nervous system, are far from being reliable dynamical elements. How can networks of unreliable elements perform reliably? We here address this question in networks of autonomous noisy elements with fluctuating timing and study the conditions for an overall system behavior being reproducible in the presence of such noise. We find a clear distinction between reliable and unreliable dynamical attractors. In the reliable case, synchrony is sustained in the network, whereas in the unreliable scenario, fluctuating timing of single elements can gradually desynchronize the system, leading to nonreproducible behavior. The likelihood of reliable dynamical attractors strongly depends on the underlying topology of a network. Comparing with the observed architectures of gene regulation networks, we find that those 3-node subgraphs that allow for reliable dynamics are also those that are more abundant in nature, suggesting that specific topologies of regulatory networks may provide a selective advantage in evolution through their resistance against noise.

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.