LAUSR

Could we somehow go back in time before bacteria developed resistance to antibiotics? Mira et al. famously cast antibiotics resistance as an optimization problem called the “antibiotics time machine.” We show that such a strategy is NP-hard to compute. Antibiotics Time Machines Resistance to antibiotics in bacteria is a central problem of modern medicine. The work of Mira et al. [MCG+15], a group of biologists and mathematicians, cast undoing or avoiding antibiotics resistance as an optimization problem, dubbed the “antibiotics time machine.” Their novel approach received wide press coverage. In this article, we define such a time machine mathematically, show that such strategies are NP-hard to compute, and discuss the implications. Let us think of an antibiotic as a sieve: it kills bacteria with a certain genotype. Repeated applications of the same antibiotic result in a population without this genotype, which renders the antibiotic ineffective. Furthermore, the course of antibiotics has altered the distribution of genotypes, or, in biological terms, the fitness landscape, of our bacterial species. This is a critical problem: imagine that the pre-antibiotics bacterial population is held in equilibrium by various factors, such as natural predators, competition for resources, and so on. A new fitness landscape disrupts this equilibrium, potentially leading to a population explosion of these bacteria. One way to mitigate these consequences is to rotate the use of antibiotics that target the same genes but select for different genotypes. Mira et al. [MCG+15] considered the following model. Suppose we have a population of bacteria, all of the same unmutated genotype (called the “wild type”). We are given a set of antibiotics. For each bacterium of a given type, an antibiotic mutates it to another type with some known probability. The problem is to find a sequence of antibiotics (called a treatment plan) that maximizes the fraction of bacteria returning to the wild type. This optimal plan is called an antibiotic time machine by Mira et al., alluding to the idea of reversing unnecessary mutations induced in the bacterial population through antibiotic treatments. Here is a concrete description of the model. Let S = {1, 2,... ,d} be a set of d states, where each state is a bacterial genotype. A distribution of bacterial population Ngoc Mai Tran is assistant professor of mathematics at the University of Texas at Austin and W-2 professor (Bonn Junior Fellow) at the Hausdorff Center for Mathematics, Germany. Her email address is [email protected]. Jed Yang is visiting assistant professor of computer science at Carleton College. His email address is [email protected]. For permission to reprint this article, please contact: [email protected]. DOI: http://dx.doi.org/10.1090/noti1590 is a vector in the standard (d − 1)-dimensional simplex Δd−1 = {(x1, x2,... , xd) ∈ Rd ∣ ∑i=1 xi = 1 and xi ≥ 0 for all i}, where for s = (s1, s2,... , sd) ∈ Δd−1, si represents the fraction of the population with genotype i ∈ S. A d×d matrix is a transition matrix if each entry belongs to the interval [0, 1] and each row sums to 1. Let T be a finite set consisting of K transition matrices, each corresponding to the effect of a given antibiotic on the genotypes of the bacterial population. That is, if T = (tij) is the transition matrix corresponding to some antibiotic, then tij is the probability that a single bacterium of genotype i will have genotype j after being treated with the antibiotic. As our population consists of millions of bacteria, we can assume that the population evolves deterministically; that is, tij can be seen as the fraction of bacteria that go from genotype i to j after treatment. Thus, if the population distribution is s ∈ Δd−1 and we apply an antibiotic with transition matrix T, then the population distribution after treatment will be sT. Let s, t ∈ Δd−1 be the starting and targeted population distributions, respectively. Let N ∈ N be the length of the treatment plan. The time machine TM(d,K,N) is the solution to the following optimization problem: