An Information Theoretic Classification of Elementary Cellular Automata

E. Borriello** and S.I. Walker (2017) An Information Theoretic Classification of Elementary Cellular Automata. Complexity. Article ID 1280351


We propose a novel, information-based classification of elementary cellular automata. The classification scheme proposed circumvents the problems associated with isolating whether complexity is in fact intrinsic to a dynamical rule, or if it arises merely as a product of a complex initial state. Transfer entropy variations processed by cellular automata split the 256 elementary rules into three information classes, based on sensitivity to initial conditions. These classes form a hierarchy such that coarse-graining transitions observed among elementary rules predominately occur within each information-based class or, much more rarely, down the hierarchy.

Physical Universality, State-Dependent Dynamics and Open-Ended Evolution

A. Adams*, A. Berner*, P.C.W. Davies and S.I. Walker (2017) Physical Universality, State-Dependent Dynamics and Open-Ended Evolution. Entropy. 19(9): 461.


A major conceptual step forward in understanding the logical architecture of living systems was advanced by von Neumann with his universal constructor, a physical device capable of self-reproduction. A necessary condition for a universal constructor to exist is that the laws of physics permit physical universality, such that any transformation (consistent with the laws of physics and availability of resources) can be caused to occur. While physical universality has been demonstrated in simple cellular automata models, so far these have not displayed a requisite feature of life—namely open-ended evolution—the explanation of which was also a prime motivator in von Neumann’s formulation of a universal constructor. Current examples of physical universality rely on reversible dynamical laws, whereas it is well-known that living processes are dissipative. Here we show that physical universality and open-ended dynamics should both be possible in irreversible dynamical systems if one entertains the possibility of state-dependent laws. We demonstrate with simple toy models how the accessibility of state space can yield open-ended trajectories, defined as trajectories that do not repeat within the expected Poincaré recurrence time and are not reproducible by an isolated system. We discuss implications for physical universality, or an approximation to it, as a foundational framework for developing a physics for life.

Origins of Life: A Problem for Physics, A Key Issues Review

S.I. Walker (2017) Origins of Life: A Problem for Physics, A Key Issues Review. Reports on Progress in Physics.  80(9): 092601


The origins of life stands among the great open scientific questions of our time. While a number of proposals exist for possible starting points in the pathway from non-living to living matter, these have so far not achieved states of complexity that are anywhere near that of even the simplest living systems. A key challenge is identifying the properties of living matter that might distinguish living and non-living physical systems such that we might build new life in the lab. This review is geared towards covering major viewpoints on the origin of life for those new to the origin of life field, with a forward look towards considering what it might take for a physical theory that universally explains the phenomenon of life to arise from the seemingly disconnected array of ideas proposed thus far. The hope is that a theory akin to our other theories in fundamental physics might one day emerge to explain the phenomenon of life, and in turn finally permit solving its origins.

Ancestral gene regulatory networks drive cancer

K. J. Bussey, L. H. Cisneros, C. H. Linweaver, and P. C. W. Davies, PNAS 2017 114 (24) 6160-6162.


Although cancer is one of the most intensively studied phenomena in biology and occurs in almost all multicellular species (1, 2), an explanation for its existence and properties within the context of evolutionary history has received comparatively little attention. However, it is widely recognized that progress in treatment and prevention depends on a deeper understanding of the biology of cancer (3).

Many of the hallmarks of cancer (4, 5) are reminiscent of unicellular life, suggesting that neoplasms represent a type of throwback or reexpression of ancestral traits. Theodore Boveri first suggested that cancer recapitulates ancient phenotypes (6). This basic idea has recently been developed into the atavistic theory of cancer, which seeks to trace cancer’s deep evolutionary roots to make specific predictions about gene expression in tumorigenesis (7, 8). The atavistic theory postulates that the biological origin of cancer can be found in the early transitional phase from unicellularity (UC) to multicellularity (MC), before the emergence of complex metazoans about 600 Mya. These ancestral traits reappear because the regulation that suppresses them or restricts them to specific contexts (e.g., embryogenesis or wound-healing) becomes disrupted. In broad terms, the atavistic theory predicts up-regulation of genes with UC evolutionary origins and down-regulation of genes that evolved after the advent of MC (Fig. 1). The work of Trigos et al. (9), reported in PNAS, sets out to test this prediction.

Ancient genes establish stress-induced mutation as a hallmark of cancer

Cisneros, L., Bussey, K. J., Orr, A. J., Miočević, M., Lineweaver, C. H., & Davies, P. (2017). Ancient genes establish stress-induced mutation as a hallmark of cancer. PloS One, 12(4), e0176258


Cancer is sometimes depicted as a reversion to single cell behavior in cells adapted to live in a multicellular assembly. If this is the case, one would expect that mutation in cancer disrupts functional mechanisms that suppress cell-level traits detrimental to multicellularity. Such mechanisms should have evolved with or after the emergence of multicellularity. This leads to two related, but distinct hypotheses: 1) Somatic mutations in cancer will occur in genes that are younger than the emergence of multicellularity (1000 million years [MY]); and 2) genes that are frequently mutated in cancer and whose mutations are functionally important for the emergence of the cancer phenotype evolved within the past 1000 million years, and thus would exhibit an age distribution that is skewed to younger genes. In order to investigate these hypotheses we estimated the evolutionary ages of all human genes and then studied the probability of mutation and their biological function in relation to their age and genomic location for both normal germline and cancer contexts. We observed that under a model of uniform random mutation across the genome, controlled for gene size, genes less than 500 MY were more frequently mutated in both cases. Paradoxically, causal genes, defined in the COSMIC Cancer Gene Census, were depleted in this age group. When we used functional enrichment analysis to explain this unexpected result we discovered that COSMIC genes with recessive disease phenotypes were enriched for DNA repair and cell cycle control. The non-mutated genes in these pathways are orthologous to those underlying stress-induced mutation in bacteria, which results in the clustering of single nucleotide variations. COSMIC genes were less common in regions where the probability of observing mutational clusters is high, although they are approximately 2-fold more likely to harbor mutational clusters compared to other human genes. Our results suggest this ancient mutational response to stress that evolved among prokaryotes was co-opted to maintain diversity in the germline and immune system, while the original phenotype is restored in cancer. Reversion to a stress-induced mutational response is a hallmark of cancer that allows for effectively searching “protected” genome space where genes causally implicated in cancer are located and underlies the high adaptive potential and concomitant therapeutic resistance that is characteristic of cancer.