Artem Kaznatcheev

Mathematical modeling plays an important role in our understanding and targeting therapy resistance mechanisms in cancer. The polymorphic Gompertzian model, analyzed theoretically by Viossat and Noble, describes a heterogeneous cancer population consisting of therapy sensitive and resistant cells. This theoretically promising model has not previously been validated with real-world data. In this study, we provide this validation. We demonstrate that the polymorphic Gompertzian model successfully captures trends in both in vitro and in vivo data on non-small cell lung cancer (NSCLC) dynamics under treatment. Additionally, for the in vivo data of tumor dynamics in patients undergoing treatment, we compare the polymorphic Gompertzian model to the classical oncologic models, which were previously identified as the models that fit this data best. We show that the polymorphic Gompertzian model can successfully capture the U-shape trend in tumor size during cancer relapse, which can not be fitted with the classical oncologic models. In general, the polymorphic Gompertzian model corresponds well to both in vitro and in vivo real-world data, suggesting it as a candidate for improving the efficacy of cancer therapy, for example through evolutionary/adaptive therapies.

Natural selection enriches genotypes that are well-adapted to their environment. Over successive generations, these changes to the frequencies of types accumulate information about the selective conditions. Thus, we can think of selection as an algorithm by which populations acquire information about their environment. Kimura (1961) pointed out that every bit of information that the population gains this way comes with a minimum cost in terms of unrealized fitness (substitution load). Due to the gradual nature of selection and ongoing mismatch of types with the environment, a population that is still gaining information about the environment has lower mean fitness than a counter-factual population that already has this information. This has been an influential insight, but here we find that experimental evolution of Escherichia coli with mutations in a RNA polymerase gene ( rpoB ) violates Kimura’s basic theory. To overcome the restrictive assumptions of Kimura’s substitution load and develop a more robust measure for the cost of selection, we turn to ideas from computational learning theory. We reframe the ‘learning problem’ faced by an evolving population as a population versus environment (PvE) game, which can be applied to settings beyond Kimura’s theory – such as stochastic environments, frequency-dependent selection, and arbitrary environmental change. We show that the learning theoretic concept of ‘regret’ measures relative lineage fitness and rigorously captures the efficiency of selection as a learning process. This lets us establish general bounds on the cost of information acquisition by natural selection. We empirically validate these bounds in our experimental system, showing that computational learning theory can account for the observations that violate Kimura’s theory. Finally, we note that natural selection is a highly effective learning process in that selection is an asymptotically optimal algorithm for the problem faced by evolving populations, and no other algorithm can consistently outperform selection in general. Our results highlight the centrality of information to natural selection and the value of computational learning theory as a perspective on evolutionary biology.

In this study, we experimentally measure the frequency-dependent interactions between a gefitinib-resistant non–small cell lung cancer population and its sensitive ancestor via the evolutionary game assay. We show that cost of resistance is insufficient to accurately predict competitive exclusion and that frequency-dependent growth rate measurements are required. Using frequency-dependent growth rate data, we then show that gefitinib treatment results in competitive exclusion of the ancestor, while the absence of treatment results in a likely, but not guaranteed, exclusion of the resistant strain. Then, using simulations, we demonstrate that incorporating ecological growth effects can influence the predicted extinction time. In addition, we show that higher drug concentrations may not lead to the optimal reduction in tumor burden. Together, these results highlight the potential importance of frequency-dependent growth rate data for understanding competing populations, both in the laboratory and as we translate adaptive therapy regimens to the clinic.

We show that as game theory was transferred from mathematical oncology to experimental cancer biology, a new mode of inquiry was created. Modeling was replaced by measuring. The game measured by a game assay can serve as a bridge that allows knowledge to flow backwards from target (cancer research) to source (game theory). Our finding suggests that the conformist and creative (Houkes and Zwart 2019) types of transfer need to be augmented. We conclude by introducing the expansive and transformative types to get a four-tier typology of knowledge transfer.

Local search is widely used to solve combinatorial optimisation problems and to model biological evolution, but the performance of local search algorithms on different kinds of fitness landscapes is poorly understood. Here we consider how fitness landscapes can be represented using valued constraints, and investigate what the structure of such representations reveals about the complexity of local search. First, we show that for fitness landscapes representable by binary Boolean valued constraints there is a minimal necessary constraint graph that can be easily computed. Second, we consider landscapes as equivalent if they allow the same (improving) local search moves; we show that a minimal constraint graph still exists, but is NP-hard to compute. We then develop several techniques to bound the length of any sequence of local search moves. We show that such a bound can be obtained from the numerical values of the constraints in the representation, and show how this bound may be tightened by considering equivalent representations. In the binary Boolean case, we prove that a degree 2 or treestructured constraint graph gives a quadratic bound on the number of improving moves made by any local search; hence, any landscape that can be represented by such a model will be tractable for any form of local search. Finally, we build two families of examples to show that the conditions in our tractability results are essential. With domain size three, even just a path of binary constraints can model a landscape with an exponentially long sequence of improving moves. With a treewidth-two constraint graph, even with a maximum degree of three, binary Boolean constraints can model a landscape with an exponentially long sequence of improving moves.

Local search is widely used to solve combinatorial optimisation problems and to model biological evolution, but the performance of local search algorithms on different kinds of fitness landscapes is poorly understood. Here we consider how fitness landscapes can be represented using valued constraints, and investigate what the structure of such representations reveals about the complexity of local search. First, we show that for fitness landscapes representable by binary Boolean valued constraints there is a minimal necessary constraint graph that can be easily computed. Second, we consider landscapes as equivalent if they allow the same (improving) local search moves; we show that a minimal constraint graph still exists, but is NP-hard to compute. We then develop several techniques to bound the length of any sequence of local search moves. We show that such a bound can be obtained from the numerical values of the constraints in the representation, and show how this bound may be tightened by considering equivalent representations. In the binary Boolean case, we prove that a degree 2 or tree-structured constraint graph gives a quadratic bound on the number of improving moves made by any local search; hence, any landscape that can be represented by such a model will be tractable for any form of local search. Finally, we build two families of examples to show that the conditions in our tractability results are essential. With domain size three, even just a path of binary constraints can model a landscape with an exponentially long sequence of improving moves. With a treewidth-two constraint graph, even with a maximum degree of three, binary Boolean constraints can model a landscape with an exponentially long sequence of improving moves.

Valiant [1] proposed to treat Darwinian evolution as a special kind of computational learning from statistical queries. The statistical queries represent a genotype’s fitness over a distribution of challenges. And this distribution of challenges along with the best response to them specify a given abiotic environment or static fitness landscape. Valiant’s model distinguished families of environments that are “adaptable-to” from those that are not. But this model of evolution omits the vital ecological interactions between different evolving agents – it neglects the rich biotic environment that is central to the struggle for existence. In this article, I extend algorithmic Darwinism to include the ecological dynamics of frequency-dependent selection as a population-dependent bias to the distribution of challenges that specify an environment. Thus, extended algorithmic Darwinism suggests extended statistical queries rather than just statistical queries as the appropriate model for eco-evo dynamics. This extended algorithmic Darwinism replaces simple invasion of wild-type by a mutant-type of higher scalar fitness with an evolutionary game between wild-type and mutant-type based on their frequency-dependent fitness function. To analyze this model, I develop a game landscape view of evolution, as a generalization of the classic fitness landscape approach. I show that this model of eco-evo dynamics on game landscapes can provide an exponential speed-up over the purely evolutionary dynamics of the strict algorithmic Darwinism. In particular, I prove that the Parity environment – which is known to be not adaptable-to under strict algorithmic Darwinism – is adaptable-to by eco-evo dynamics. Thus, the ecology of frequency-dependent selection does not just increase the tempo of evolution, but fundamentally transforms its mode. This happens even if frequency-dependence is restricted to short-time scales – such short bursts of frequency-dependent selection can have a transformative effect on the ability of populations to adapt to their environments in the long-term. Unlike typical learning algorithms, the eco-evo dynamic for adapting to the Parity environment does not rely on Gaussian elimination. Instead, the dynamics proceed by simple isotropic mutations and selection in finite populations of just two types (the resident wild-type and invading mutant). The resultant process has two stages: (1) a quick stage of point-mutations that moves the population to one of exponentially many local fitness peaks; followed by (2) a slower stage where each ‘step’ follows a double-mutation by a point-mutation. This second stage allows the population to hop between local fitness peaks to reach the unique global fitness peak in polynomial time. The evolutionary game dynamics of finite populations are essential for finding a short adaptive path to the global fitness peak during the second stage of the adaptation process. This highlights the rich interface between computational learning theory, analysis of algorithms, evolutionary games, and long-term evolution.

Experiments show that evolutionary fitness landscapes can have a rich combinatorial structure due to epistasis. For some landscapes, this structure can produce a computational constraint that prevents evolution from finding local fitness optima—thus overturning the traditional assumption that local fitness peaks can always be reached quickly if no other evolutionary forces challenge natural selection. Here, I introduce a distinction between easy landscapes of traditional theory where local fitness peaks can be found in a moderate number of steps, and hard landscapes where finding local optima requires an infeasible amount of time. Hard examples exist even among landscapes with no reciprocal sign epistasis; on these semismooth fitness landscapes, strong selection weak mutation dynamics cannot find the unique peak in polynomial time. More generally, on hard rugged fitness landscapes that include reciprocal sign epistasis, no evolutionary dynamics—even ones that do not follow adaptive paths—can find a local fitness optimum quickly. Moreover, on hard landscapes, the fitness advantage of nearby mutants cannot drop off exponentially fast but has to follow a power-law that long-term evolution experiments have associated with unbounded growth in fitness. Thus, the constraint of computational complexity enables open-ended evolution on finite landscapes. Knowing this constraint allows us to use the tools of theoretical computer science and combinatorial optimization to characterize the fitness landscapes that we expect to see in nature. I present candidates for hard landscapes at scales from single genes, to microbes, to complex organisms with costly learning (Baldwin effect) or maintained cooperation (Hankshaw effect). Just how ubiquitous hard landscapes (and the corresponding ultimate constraint on evolution) are in nature becomes an open empirical question.