Evolutionary graph theory: breaking the symmetry between interaction and replacement

We study evolutionary dynamics in a population whose structure is given by two graphs: the interaction graph determines who plays with whom in an evolutionary game; the replacement graph specifies the geometry of evolutionary competition and updating. First, we calculate the fixation probabilities of frequency dependent selection between two strategies or phenotypes. We consider three different update mechanisms: birth-death, death-birth and imitation. Then, as a particular example, we explore the evolution of cooperation. Suppose the interaction graph is a regular graph of degree h, the replacement graph is a regular graph of degree g and the overlap between the two graphs is a regular graph of degree l. We show that cooperation is favored by natural selection if b/c>hg/l. Here, b and c denote the benefit and cost of the altruistic act. This result holds for death-birth updating, weak-selection and large population size. Note that the optimum population structure for cooperators is given by maximum overlap between the interaction and the replacement graph (g=h=l), which means that the two graphs are identical. We also prove that a modified replicator equation can describe how the expected values of the frequencies of an arbitrary number of strategies change on replacement and interaction graphs: the two graphs induce a transformation of the payoff matrix.     

Sparse networks of directly coupled,polymorphic, and functional side chains in allosteric proteins

Recent studies have highlighted the role of coupled side‐chain fluctuations alone in the allosteric behavior of proteins. Moreover, examination of X‐ray crystallography data has recently revealed new information about the prevalence of alternate side‐chain conformations (conformational polymorphism), and attempts have been made to uncover the hidden alternate conformations from X‐ray data. Hence, new computational approaches are required that consider the polymorphic nature of the side chains, and incorporate the effects of this phenomenon in the study of information transmission and functional interactions of residues in a molecule. These studies can provide a more accurate understanding of the allosteric behavior. In this article, we first present a novel approach to generate an ensemble of conformations and an efficient computational method to extract direct couplings of side chains in allosteric proteins, and provide sparse network representations of the couplings. We take the side‐chain conformational polymorphism into account, and show that by studying the intrinsic dynamics of an inactive structure, we are able to construct a network of functionally crucial residues. Second, we show that the proposed method is capable of providing a magnified view of the coupled and conformationally polymorphic residues. This model reveals couplings between the alternate conformations of a coupled residue pair. To the best of our knowledge, this is the first computational method for extracting networks of side chains' alternate conformations. Such networks help in providing a detailed image of side‐chain dynamics in functionally important and conformationally polymorphic sites, such as binding and/or allosteric sites. Proteins 2015; 83:497–516. © 2014 Wiley Periodicals, Inc.     

Quantitative delineation of how breathing motions open ligand migration channels in myoglobin and its mutants

Ligand migration and binding are central to the biological functions of many proteins such as myoglobin (Mb) and it is widely thought that protein breathing motions open up ligand channels dynamically. However, how a protein exerts its control over the opening and closing of these channels through its intrinsic dynamics is not fully understood. Specifically, a quantitative delineation of the breathing motions that are needed to open ligand channels is lacking. In this work, we present and apply a novel normal mode‐based method to quantitatively delineate what and how breathing motions open ligand migration channels in Mb and its mutants. The motivation behind this work springs from the observation that normal mode motions are closely linked to the breathing motions that are thought to open ligand migration channels. In addition, the method provides a direct and detailed depiction of the motions of each and every residue that lines a channel and can identify key residues that play a dominating role in regulating the channel. The all‐atom model and the full force‐field employed in the method provide a realistic energetics on the work cost required to open a channel, and as a result, the method can be used to efficiently study the effects of mutations on ligand migration channels and on ligand entry rates. Our results on Mb and its mutants are in excellent agreement with MD simulation results and experimentally determined ligand entry rates. Proteins 2015; 83:757–770. © 2015 Wiley Periodicals, Inc.     

Experimental evidence for the effect of habitat loss on the dynamics of migratory networks

Migratory animals present a unique challenge for understanding the consequences of habitat loss on population dynamics because individuals are typically distributed over a series of interconnected breeding and non‐breeding sites (termed migratory network). Using replicated breeding and non‐breeding populations of Drosophila melanogaster and a mathematical model, we investigated three hypotheses to explain how habitat loss influenced the dynamics of populations in networks with different degrees of connectivity between breeding and non‐breeding seasons. We found that habitat loss increased the degree of connectivity in the network and influenced population size at sites that were not directly connected to the site where habitat loss occurred. However, connected networks only buffered global population declines at high levels of habitat loss. Our results demonstrate why knowledge of the patterns of connectivity across a species range is critical for predicting the effects of environmental change and provide empirical evidence for why connected migratory networks are commonly found in nature.     

用原图-对偶图法设计内部间隔最小的自然保护区

生境破碎是导致生物多样性损失的重要原因之一,在设计自然保护区时设法减少生境破碎是提高保护区有效性的重要方法.由于经济资源或地理因素制约不可能把连续的大片土地都划为保护区时,设计一个由相互分离的几部分组成的保护区是更为现实的做法.选择地块组成内部间隔最小的保护区是减少破碎化的一个重要途径,但结合空间特征的保护区地块选择模...     

Computation of Minimal Uniform Transmission Range in Ad Hoc Wireless Networks

Power conservation is a critical issue for ad hoc wireless networks. The main objective of the paper is to find the minimum uniform transmission range of an ad hoc wireless network, where each node uses the same transmission power, while maintaining network connectivity. Three different algorithms, Prims Minimum Spanning Tree (MST), its extension with Fibonacci heap implementation, and an area-based binary search are developed to solve the problem. Their performance is compared by simulation study together with Kruskals MST, a known solution proposed by Ramanathan and Rosales-Hain for topology control by transmission power adjustment, and an edge-based binary search used by the same study in order to find the per-node-minimality after Kruskals algorithm is applied. Our results show that Prims MST outperforms both Kruskals MST and the two binary searches. The performance between Prims MST implemented with binary heap and Fibonacci heap is fairly close, with the Fibonacci implementation slightly outperforming the other.Qing Dai received her M.S. degree in Computer Science from Florida Atlantic University on August 2003, and M.S. degree in Microbiology from Upstate University on July 2000. She is currently a software engineer at Motorola, Plantation, FL.Jie Wu is a Professor at Department of Computer Science and Engineering, Florida Atlantic University. He has published over 200 papers in various journals and conference proceedings. His research interests are in the areas of wireless networks and mobile computing, routing protocols, fault-tolerant computing, and interconnection networks. He served on many conference organization committees. Dr. Wu is on the editorial board of IEEE Transactions on Parallel and Distributed Systems and was a co-guest-editor of IEEE Computer and Journal of Parallel and Distributed Computing. He is the author of the text Distributed System Design published by the CRC press. He was also the recipient of the 1996–97 and 2001–2002 Researcher of the Year Award at Florida Atlantic University. Dr. Wu has served as an IEEE Computer Society Distinguished Visitor. He is a Member of ACM and a Senior Member of IEEE.     

Proteomic traces of speciation

Recent work has shown that the network of structural similarity between protein domains exhibits a power-law distribution of edges per node. The scale-free nature of this graph, termed the protein domain universe graph or PDUG, may be reproduced via a divergent model of structural evolution. The performance of this model, however, does not preclude the existence of a successful convergent model. To further resolve the issue of protein structural evolution, we explore the predictions of both convergent and divergent models directly. We show that when nodes from the PDUG are partitioned into subgraphs on the basis of their occurrence in the proteomes of particular organisms, these subgraphs exhibit a scale-free nature as well. We explore a simple convergent model of structural evolution and find that the implications of this model are inconsistent with features of these organismal subgraphs. Importantly, we find that biased convergent models are inconsistent with our data. We find that when speciation mechanisms are added to a simple divergent model, subgraphs similar to the organismal subgraphs are produced, demonstrating that dynamic models can easily explain the distributions of structural similarity that exist within proteomes. We show that speciation events must be included in a divergent model of structural evolution to account for the non-random overlap of structural proteomes. These findings have implications for the long-standing debate over convergent and divergent models of protein structural evolution, and for the study of the evolution of organisms as a whole.     

Virtual identification of essential proteins within the protein interaction network of yeast

Topological analysis of large scale protein-protein interaction networks (PINs) is important for understanding the organizational and functional principles of individual proteins. The number of interactions that a protein has in a PIN has been observed to be correlated with its indispensability. Essential proteins generally have more interactions than the nonessential ones. We show here that the lethality associated with removal of a protein from the yeast proteome correlates with different centrality measures of the nodes in the PIN, such as the closeness of a protein to many other proteins, or the number of pairs of proteins which need a specific protein as an intermediary in their communications, or the participation of a protein in different protein clusters in the PIN. These measures are significantly better than random selection in identifying essential proteins in a PIN. Centrality measures based on graph spectral properties of the network, in particular the subgraph centrality, show the best performance in identifying essential proteins in the yeast PIN. Subgraph centrality gives important structural information about the role of individual proteins, and permits the selection of possible targets for rational drug discovery through the identification of essential proteins in the PIN.     

Evolutionary dynamics in structured populations

Evolutionary dynamics shape the living world around us. At the centre of every evolutionary process is a population of reproducing individuals. The structure of that population affects evolutionary dynamics. The individuals can be molecules, cells, viruses, multicellular organisms or humans. Whenever the fitness of individuals depends on the relative abundance of phenotypes in the population, we are in the realm of evolutionary game theory. Evolutionary game theory is a general approach that can describe the competition of species in an ecosystem, the interaction between hosts and parasites, between viruses and cells, and also the spread of ideas and behaviours in the human population. In this perspective, we review the recent advances in evolutionary game dynamics with a particular emphasis on stochastic approaches in finite sized and structured populations. We give simple, fundamental laws that determine how natural selection chooses between competing strategies. We study the well-mixed population, evolutionary graph theory, games in phenotype space and evolutionary set theory. We apply these results to the evolution of cooperation. The mechanism that leads to the evolution of cooperation in these settings could be called ‘spatial selection’: cooperators prevail against defectors by clustering in physical or other spaces.