Deep sequencing has enabled the investigation of a wide range of environmental microbial ecosystems, but the high memory requirements for de novo assembly of short-read shotgun sequencing data from these complex populations are an increasingly large practical barrier. Here we introduce a memory-efficient graph representation with which we can analyze the k -mer connectivity of metagenomic samples. The graph representation is based on a probabilistic data structure, a Bloom filter, that allows us to efficiently store assembly graphs in as little as 4 bits per k -mer, albeit inexactly. We show that this data structure accurately represents DNA assembly graphs in low memory. We apply this data structure to the problem of partitioning assembly graphs into components as a prelude to assembly, and show that this reduces the overall memory requirements for de novo assembly of metagenomes. On one soil metagenome assembly, this approach achieves a nearly 40-fold decrease in the maximum memory requirements for assembly. This probabilistic graph representation is a significant theoretical advance in storing assembly graphs and also yields immediate leverage on metagenomic assembly.
Evolutionary game theory is a successful mathematical framework geared towards understanding the selective pressures that affect the evolution of the strategies of agents engaged in interactions with potential conflicts. While a mathematical treatment of the costs and benefits of decisions can predict the optimal strategy in simple settings, more realistic settings such as finite populations, non-vanishing mutations rates, stochastic decisions, communication between agents, and spatial interactions, require agent-based methods where each agent is modeled as an individual, carries its own genes that determine its decisions, and where the evolutionary outcome can only be ascertained by evolving the population of agents forward in time. While highlighting standard mathematical results, we compare those to agent-based methods that can go beyond the limitations of equations and simulate the complexity of heterogeneous populations and an ever-changing set of interactors. We conclude that agent-based methods can predict evolutionary outcomes where purely mathematical treatments cannot tread (for example in the weak selection-strong mutation limit), but that mathematics is crucial to validate the computational simulations.
Zero-determinant strategies are a new class of probabilistic and conditional strategies that are able to unilaterally set the expected payoff of an opponent in iterated plays of the Prisoner's Dilemma irrespective of the opponent's strategy (coercive strategies), or else to set the ratio between the player's and their opponent's expected payoff (extortionate strategies). Here we show that zero-determinant strategies are at most weakly dominant, are not evolutionarily stable, and will instead evolve into less coercive strategies. We show that zero-determinant strategies with an informational advantage over other players that allows them to recognize each other can be evolutionarily stable (and able to exploit other players). However, such an advantage is bound to be short-lived as opposing strategies evolve to counteract the recognition.
6 August 2013 in Journal of The Royal Society Interface
Swarming behaviours in animals have been extensively studied owing to their implications for the evolution of cooperation, social cognition and predator–prey dynamics. An important goal of these studies is discerning which evolutionary pressures favour the formation of swarms. One hypothesis is that swarms arise because the presence of multiple moving prey in swarms causes confusion for attacking predators, but it remains unclear how important this selective force is. Using an evolutionary model of a predator–prey system, we show that predator confusion provides a sufficient selection pressure to evolve swarming behaviour in prey. Furthermore, we demonstrate that the evolutionary effect of predator confusion on prey could in turn exert pressure on the structure of the predator's visual field, favouring the frontally oriented, high-resolution visual systems commonly observed in predators that feed on swarming animals. Finally, we provide evidence that when prey evolve swarming in response to predator confusion, there is a change in the shape of the functional response curve describing the predator's consumption rate as prey density increases. Thus, we show that a relatively simple perceptual constraint—predator confusion—could have pervasive evolutionary effects on prey behaviour, predator sensory mechanisms and the ecological interactions between predators and prey.
Biological networks have evolved to be highly functional within uncertain environments while remaining extremely adaptable. One of the main contributors to the robustness and evolvability of biological networks is believed to be their modularity of function, with modules defined as sets of genes that are strongly interconnected but whose function is separable from those of other modules. Here, we investigate the in silico evolution of modularity and robustness in complex artificial metabolic networks that encode an increasing amount of information about their environment while acquiring ubiquitous features of biological, social, and engineering networks, such as scale-free edge distribution, small-world property, and fault-tolerance. These networks evolve in environments that differ in their predictability, and allow us to study modularity from topological, information-theoretic, and gene-epistatic points of view using new tools that do not depend on any preconceived notion of modularity. We find that for our evolved complex networks as well as for the yeast protein–protein interaction network, synthetic lethal gene pairs consist mostly of redundant genes that lie close to each other and therefore within modules, while knockdown suppressor gene pairs are farther apart and often straddle modules, suggesting that knockdown rescue is mediated by alternative pathways or modules. The combination of network modularity tools together with genetic interaction data constitutes a powerful approach to study and dissect the role of modularity in the evolution and function of biological networks. The modular organization of cells is not immediately obvious from the network of interacting genes, proteins, and molecules. A new window into cellular modularity is opened up by genetic data that identifies pairs of genes that interact either directly or indirectly to provide robustness to cellular function. Such pairs can map out the modular nature of a network if we understand how they relate to established mathematical clustering methods applied to networks to identify putative modules. We can test the relationship between genetically interacting pairs and modules on artificial data: large networks of interacting proteins and molecules that were evolved within an artificial chemistry and genetics, and that pass the standard tests for biological networks. Modularity evolves in these networks in order to deal with a multitude of functional goals, with a degree depending on environmental variability. Relationships between genetically interacting pairs and modules similar to those displayed by the artificial gene networks are found in the protein–protein interaction network of baker's yeast. The evolution of complex functional biological networks in silico provides an opportunity to develop and test new methods and tools to understand the complexity of biological systems at the network level.
22 June 2011 in Proceedings Of The Royal Society B-Biological Sciences
Evolutionary adaptation is often likened to climbing a hill or peak. While this process is simple for fitness landscapes where mutations are independent, the interaction between mutations (epistasis) as well as mutations at loci that affect more than one trait (pleiotropy) are crucial in complex and realistic fitness landscapes. We investigate the impact of epistasis and pleiotropy on adaptive evolution by studying the evolution of a population of asexual haploid organisms (haplotypes) in a model of N interacting loci, where each locus interacts with K other loci. We use a quantitative measure of the magnitude of epistatic interactions between substitutions, and find that it is an increasing function of K. When haplotypes adapt at high mutation rates, more epistatic pairs of substitutions are observed on the line of descent than expected. The highest fitness is attained in landscapes with an intermediate amount of ruggedness that balance the higher fitness potential of interacting genes with their concomitant decreased evolvability. Our findings imply that the synergism between loci that interact epistatically is crucial for evolving genetic modules with high fitness, while too much ruggedness stalls the adaptive process.