Elements of biological computation & stochastic thermodynamics of life

This week, I was visiting the Santa Fe Institute for a workshop organized by Albert Kao, Jessica Flack, and David Wolpert on “What is biological computation?” (11 – 13 September 2019). It was an ambitious question and I don’t think that we were able to answer it in just three days of discussion, but I think that we all certainly learnt a lot.

At least, I know that I learned a lot of new things.

The workshop had around 34 attendees from across the world, but from the reaction on twitter it seems like many more would have been eager to attend also. Hence, both to help synchronize the memory networks of all the participants and to share with those who couldn’t attend, I want to use this series of blog post to jot down some of the topics that were discussed at the meeting.

During the conference, I was live tweeting. So if you prefer my completely raw, unedited impressions in tweet form then you can take a look at those threads for Wednesday (14 tweets), Thursday (15 tweets), and Friday (31 tweets). The workshop itself was organized around discussion, and the presentations were only seeds. Unfortunately, my live tweeting and this post are primarily limited to just the presentations. But I will follow up with some synthesis and reflection in the future.

Due to the vast amount discussed during the workshop, I will focus this post on just the first day. I’ll follow with posts on the other days later.

It is also important to note that this is the workshop through my eyes. And thus this retelling is subject to the limits of my understanding, notes, and recollection. In particular, I wasn’t able to follow the stochastic thermodynamics that dominated the afternoon of the first day. And although I do provide some retelling, I hope that I can convince one of the experts to provide a more careful blog post on the topic.

On Wednesday, Peter Stadler opened the workshop with a tutorial on the elements of computation. He outlined an extended Chomsky hierarchy (although expressed in terms of the corresponding machine models, not grammars) and discussed where various processes of molecular biology fall within this hierarchy. In other words, where in this ladder of computation should we see individual cells?

Stadler suggested that transcription was at the level of combinatorial logic. Gene regulatory networks ranged from the level of DFAs for simple ones to push-down automata for more complicated networks. And (de)modification of enzymes ad methylation of DNA — or the chromatin computer — was Turing-complete (Bryant, 2012).

In the discussion, I expressed concerns about how coarse this hierarchy was. In particular, we seem to lose most of post-70s computer science in the big gap between push-down automata and Turing machines. In general, it seemed like the overly coarse Chomsky hierarchy reappeared as a punching bad in many later discussions. And if there was any agreement during the workshop, it seemed to be that we need to move on from computability to more fine-grained computational complexity. Or maybe something even more refined and specialized for the purposes of distributed computing, in particular. Turing machines were seen as “shutting out the world”, and there was a big push to focus on models of explicitly concurrent systems instead.

After a short break, Michael Levin took the flow to discuss morphological computation: how the structuring of morphology, development, and self-repair computes within us. He focused on experimental biology, giving us examples from caterpillars liquefying their brains as they turn into butterflies to flatworms regrowing their heads after they explode from barium poisoning. Levin was especially focused on how these biological case studies highlighted the organism’s ability to self-model. Or in the language of Turing Machines: to receive themselves as their own input.

Levin gave many examples, but one of the most dramatic was the salamander. These animals are famous for regrowing their limbs, but the extreme robustness of this regrowth is seldom discussed. In particular, if you attach a salamander’s severed tail to the stump of a lost leg then over time that tail will transform into a new leg. For Levin, this was morphological self-surveillance: the process of morphological development could survey itself and remodel towards globally correct structured. And this wasn’t limited to salamanders. It also occurred in tadpoles as they reconfigured their faces to become frogs, and in flatworms.

For me, planarian flatworms were the main highlight of Levin’s talk. These are multicellular organisms that reproduce by ripping themselves in half and then having each half regrow into a full planarian. The experimental record was from the early 19th century, where a single planarian was cut up into over 200 pieces with each piece regenerating into a new functional animal. This amazing regenerative ability makes planarians immortal, but it also means that their somatic tissue has been around for thousands of years and is thus full of mutations. Their genome is a mess. We can’t even say how many chromosomes a planarian has because the number is different between different cells in the same animal. This is a huge conceptual challenge for people who are overly obsessed with genomics.

Most remarkable is the robustness and flexibility of planarian regeneration. For example, large concentrations of barium mess with most biological function in most animals. In the case of planarian’s, it makes their heads explode. Yet after about 12 days, the animal will regrow a head that is resistant to barium. Since barium is not a chemical that the organisms ever encountered in their evolutionary history, this is an example of true novelty being generated by morphogenesis. The flexibility of planarian morphogenesis can also be harnessed for engineering purposes. Levin is able to grow planarians with 2 or 3 heads (and thus 2 or 3 brains) that continue to live and flourish in their environment.

Jessica Flack closed the morning session with a discussion of the different ways that computer science concepts are used in biology. She favours the programmatic approach: borrow ing computer science concepts to work out practical bio problems. But she wants to make the computer science more foundational and precise. Especially for collectives. This urge for a more foundational role for computer science is similar to my advocacy for algorithmic biology as a foundational alternatively to the practical focus of computational biology.

A big focus for Flack’s talk was the shift of emphasis between microscopic and — what she called — mesoscopic levels of description, with coarse-graining as the connection. And in the case of biology and computation, the information flow proceeding not only from the microscopic up to the mesoscopic but also from the mesaoscopic down to the microscopic. As I’ve stressed before, I don’t think that coarse-graining is the only mapping that we should consider — especially when abstraction is available. And Stephanie Forrest echoed this sentiment in the discussion arguing that “abstraction is exactly what computation can contribute to biology.”

The central aspect of Flack’s presentation, however, wasn’t the details of the mapping but the feedback between microscopic and mesoscopic theory. Her emphasis was to not just start with the micrsocopic theory and work up to the mesoscopic but to look at the feedback between the levels. It is important to use a good mesoscopic theory to then identify the relevant microscopic states. For me, this was best enacted by DeDeo, Krakauer & Flack’s (2010) inductive game theory. I have recently also worked towards this end by defining effective games as an empirical abstraction (Kaznatcheev, 2017; 2018), and starting with careful measurements of them via the game assay for type-type interactions (Kaznatcheev et al., 2019) before trying to work down to the microscopic level of cell-cell interaction.

Flack finished with the four types of questions we might ask of biology. We might ask about capacity; we might ask about satisficing, efficiency, and optimality; we might ask about mechanism and architecture; and we might ask about evolution. Computer science can help us answer all four kinds of questions.

After lunch, we focused more formally on how to coarse grain the microscopic into the mesoscopic using stochastic thermodynamics. Massimiliano Esposito gave the opening tutorial and explained how this framework can help us connect thermodynamics and information. Whereas traditional thermodynamics applies to extremely large systems, stochastic thermodynamics is the thermodynamics of small systems. For an exhaustive review, see Seifert (2012) and for an introduction see Van den Broeck & Esposito (2015). Stochastic thermodynamic’s central concept is local detailed balance that allows one to assign energies to all the chemical species that are being modeled. This allows us to look at non-equilibrium systems and use the non-equilibrium state as a resource to be used or wasted. In particular, we can information to extract work and measurement to ‘create’ energy. This allows us to have a generalized second law of thermodynamics: information is an upper bound on work.

During the tutorial some controversy erupted on if we could think of Maxwell’s demon (or better yet, Szilard’s engine) as the conceptually minimal form of life: one bit of measurement, one bit of action, one bit of memory. Tali Tishby defended this position, but many were skeptical.

After, Jordan Horowitz build on Esposito’s groundwork by showing how there isn’t a single second law, but many second laws of thermodynamics. Depending on what information-like measure we use, we get different bounds on the amount of work that can be extracted using that information. Thermodynamic costs are context dependent. At least when we have some coarse-grained black boxes within our system.

Finally, David Wolpert connected this framework to standard aspects of algorithmic information theory such as Kolmogorov complexity. This allows for looking at the stochastic thermodynamics of computation (Wolpert, 2019). Wolpert started by applying this theory “under the lampost”, he showed how this approach can be used to analyze certain toy problems like circuits and DFAs. The hope is to expand this approach to real biological problems, but Wolpert left this connection to biology for Thursday.

References

Bryant, B. (2012). Chromatin computation. PloS One, 7(5): e35703.

DeDeo, S., Krakauer, D. C., & Flack, J. C. (2010). Inductive game theory and the dynamics of animal conflict. PLoS Computational Biology, 6(5): e1000782.

Kaznatcheev, A. (2017). Two conceptions of evolutionary games: reductive vs effective. bioRxiv, 231993.

Kaznatcheev, A. (2018). Effective games and the confusion over spatial structure. Proceedings of the National Academy of Sciences, 115(8), E1709-E1709.

Kaznatcheev, A., Peacock, J., Basanta, D., Marusyk, A., & Scott, J. G. (2019). Fibroblasts and alectinib switch the evolutionary games played by non-small cell lung cancer. Nature Ecology & Evolution, 3(3): 450.

Seifert, U. (2012). Stochastic thermodynamics, fluctuation theorems and molecular machines. Reports on Progress in Physics, 75(12), 126001.

Van den Broeck, C., & Esposito, M. (2015). Ensemble and trajectory thermodynamics: A brief introduction. Physica A: Statistical Mechanics and its Applications, 418, 6-16.

Wolpert, D.H. (2019). The stochastic thermodynamics of computation. Journal of Physics A: Mathematical and Theoretical, 52(19), 193001.