Introduction to Algorithmic Biology: Evolution as Algorithm

As Aaron Roth wrote on Twitter — and as I bet with my career: “Rigorously understanding evolution as a computational process will be one of the most important problems in theoretical biology in the next century. The basics of evolution are many students’ first exposure to “computational thinking” — but we need to finish the thought!”

Last week, I tried to continue this thought for Oxford students at a joint meeting of the Computational Society and Biological Society. On May 22, I gave a talk on algorithmic biology. I want to use this post to share my (shortened) slides as a pdf file and give a brief overview of the talk.

If you didn’t get a chance to attend, maybe the title and abstract will get you reading further:

Algorithmic Biology: Evolution is an algorithm; let us analyze it like one.

Evolutionary biology and theoretical computer science are fundamentally interconnected. In the work of Charles Darwin and Alfred Russel Wallace, we can see the emergence of concepts that theoretical computer scientists would later hold as central to their discipline. Ideas like asymptotic analysis, the role of algorithms in nature, distributed computation, and analogy from man-made to natural control processes. By recognizing evolution as an algorithm, we can continue to apply the mathematical tools of computer science to solve biological puzzles – to build an algorithmic biology.

One of these puzzles is open-ended evolution: why do populations continue to adapt instead of getting stuck at local fitness optima? Or alternatively: what constraint prevents evolution from finding a local fitness peak? Many solutions have been proposed to this puzzle, with most being proximal – i.e. depending on the details of the particular population structure. But computational complexity provides an ultimate constraint on evolution. I will discuss this constraint, and the positive aspects of the resultant perpetual maladaptive disequilibrium. In particular, I will explain how we can use this to understand both on-going long-term evolution experiments in bacteria; and the evolution of costly learning and cooperation in populations of complex organisms like humans.

Unsurprisingly, I’ve writen about all these topics already on TheEGG, and so my overview of the talk will involve a lot of links back to previous posts. In this way. this can serve as an analytic linkdex on algorithmic biology.

Advertisements

Four stages in the relationship of computer science to other fields

This weekend, Oliver Schneider — an old high-school friend — is visiting me in the UK. He is a computer scientist working on human-computer interaction and was recently appointed as an assistant professor at the Department of Management Sciences, University of Waterloo. Back in high-school, Oliver and I would occasionally sneak out of class and head to the University of Saskatchewan to play counter strike in the campus internet cafe. Now, Oliver builds haptic interfaces that can represent virtually worlds physically so vividly that a blind person can now play a first-person shooter like counter strike. Take a look:

Now, dear reader, can you draw a connecting link between this and the algorithmic biology that I typically blog about on TheEGG?

I would not be able to find such a link. And that is what makes computer science so wonderful. It is an extremely broad discipline that encompasses many areas. I might be reading a paper on evolutionary biology or fixed-point theorems, while Oliver reads a paper on i/o-psychology or how to cut 150 micron-thick glass. Yet we still bring a computational flavour to the fields that we interface with.

A few years ago, Karp’s (2011; Xu & Tu, 2011) wrote a nice piece about the myriad ways in which computer science can interact with other disciplines. He was coming at it from a theorist’s perspective — that is compatible with TheEGG but maybe not as much with Oliver’s work — and the bias shows. But I think that the stages he identified in the relationship between computer science and others fields is still enlightening.

In this post, I want to share how Xu & Tu (2011) summarize Karp’s (2011) four phases of the relationship between computer science and other fields: (1) numerical analysis, (2) computational science, (3) e-Science, and the (4) algorithmic lens. I’ll try to motivate and prototype these stages with some of my own examples.

Danger of motivatiogenesis in interdisciplinary work

Randall Munroe has a nice old xkcd on citogenesis: the way factoids get created from bad checking of sources. You can see the comic at right. But let me summarize the process without direct reference to Wikipedia:

1. Somebody makes up a factoid and writes it somewhere without citation.
2. Another person then uses the factoid in passing in a more authoritative work, maybe sighting the point in 1 or not.
3. Further work inherits the citation from 2, without verifying its source, further enhancing the legitimacy of the factoid.
4. The cycle repeats.

Soon, everybody knows this factoid and yet there is no ground truth to back it up. I’m sure we can all think of some popular examples. Social media certainly seems to make this sort of loop easier.

We see this occasionally in science, too. Back in 2012, Daniel Lemire provided a nice example of this with algorithms research. But usually with science factoids, it eventually gets debuked with new experiments or proofs. Mostly because it can be professionally rewarding to show that a commonly assumed factoid is actually false.

But there is a similar effect in science that seems to me even more common, and much harder to correct: motivatiogenesis.

Motivatiogenesis can be especially easy to fall into with interdisiplinary work. Especially if we don’t challenge ourselves to produce work that is an advance in both (and not just one) of the fields we’re bridging.

Personal case study on the usefulness of philosophy to biology

At the start of this month, one of my favourite blogs — Dynamic Ecology — pointed me to a great interview with Michela Massimi. She has recently won the Royal Society’s Wilkins-Bernal-Medawar Medal for the philosophy of science, and to celebrate Philip Ball interviewed her for Quanta. I recommend reading the whole interview, but for this post, I will focus on just one aspect.

Ball asked Massimi how she defends philosophy of science against dismissive comments by scientists like Feynman or Hawking. In response, she made the very important point that for the philosophy of science to be useful, it doesn’t need to be useful to science:

Dismissive claims by famous physicists that philosophy is either a useless intellectual exercise, or not on a par with physics because of being incapable of progress, seem to start from the false assumption that philosophy has to be of use for scientists or is of no use at all.

But all that matters is that it be of some use. We would not assess the intellectual value of Roman history in terms of how useful it might be to the Romans themselves. The same for archaeology and anthropology. Why should philosophy of science be any different?

Instead, philosophy is useful for humankind more generally. This is certainly true.

But even for a scientist who is only worrying about getting that next grant, or publishing that next flashy paper. For a scientist who is completely detached from the interests of humanity. Even for this scientist, I don’t think we have to concede the point on the usefulness of philosophy of science. Because philosophy, and philosophy of science in particular, doesn’t need to be useful to science. But it often is.

Here I want to give a personal example that I first shared in the comments on Dynamic Ecology.

Emotional contagion and rational argument in philosophical texts

Last week I returned to blogging with some reflections on reading and the written word more generally. Originally, I was aiming to write a response to Roger Schank’s stance that “reading is no way to learn”, but I wandered off on too many tangents for an a single post or for a coherent argument. The tangent that I left for this post is the role of emotion and personality in philosophical texts.

In my last entry, I focused on the medium independent aspects of Schank’s argument, and identified two dimensions along which a piece of media and our engagement with it can vary: (1) passive consumption versus active participation, and (2) the level of personalization. The first continuum has a clearly better end on the side of more active engagement. If we are comparing mediums then we should prefer ones that foster more active engagement from the participants. The second dimension is more ambiguous: sometimes a more general piece of media is better than a bespoke piece. What is better becomes particularly ambiguous when being forced to adapt a general approach to your special circumstances encourages more active engagement.

In this post, I will shift focus from comparing mediums to a particular aspect of text and arguments: emotional engagement. Of course, this also shows up in other mediums, but my goal this time is not to argue across mediums.

Passive vs. active reading and personalization

As you can probably tell, dear reader, recently I have been spending too much time reading and not enough time writing. The blog has been silent. What better way to break this silence than to write a defense of reading? Well, sort of. It would not be much of an eye-opener for you — nor a challenge for me — to simply argue for reading. Given how you are consuming this content, you probably already think that the written word is a worthwhile medium. Given how I am presenting myself, I probably think the same. But are our actions really an endorsement of reading or just the form of communication we begrudgingly resort to because of a lack of better alternatives?

Ostensibly this post will be a qualified defense against an attack on reading by Roger Schank at Education Outrage. Although it is probably best to read it as just a series of reflections on my own experience.^[1]

I will focus on the medium-independent aspects of learning that I think give weight to Schank’s argument: the distinction between passive and active learning, and the level of personalization. This will be followed next week by a tangent discussion on the importance of emotional aspects of the text, and close with some reflections on the role of literary value, historic context, and fiction in philosophical arguments. This last point is prompted more by my recent readings of Plato than by Schank. In other words, much like last year, I will rely on Socrates to help get me out of a writing slump.

A detailed update on readership for the first 200 posts

It is time — this is the 201st article on TheEGG — to get an update on readership since our 151st post and lament on why academics should blog. I apologize for this navel-gazing post, and it is probably of no interest to you unless you are really excited about blog statistics. I am writing this post largely for future reference and to celebrate this arbitrary milestone.

The of statistics in this article are largely superficial proxies — what does a view even mean? — and only notable because of how easy they are to track. These proxies should never be used to seriously judge academics but I do think they can serve as a useful self-tracking tool. Making your blog’s statistics available publicly can be a useful comparison for other bloggers to get an idea of what sort of readership and posting habits are typical. In keeping with this rough and lighthearted comparison, according to Jeromy Anglim’s order-of-magnitude rules of thumb, in the year since the last update the blog has been popular in terms of RSS subscribers and relatively popular in terms of annual page views.

As before, I’ll start with the public self-metrics of the viewership graph for the last 6 and a half months:

Columns are views per week at TheEGG blog since the end of August, 2014. The vertical lines separate months, and the black line is average views per day for each month. The scale for weeks is on the left, it is different from the scale for daily average, those are labeled at each height.

If you’d like to know more, dear reader, then keep reading. Otherwise, I will see you on the next post!

A year in books: philosophy, psychology, and political economy

If you follow the Julian calendar — which I do when I need a two week extension on overdue work — then today is the first day of 2015.

Happy Old New Year!

This also means that this is my last day to be timely with a yet another year-in-review post; although I guess I could also celebrate the Lunar New Year on February 19th. Last year, I made a resolution to read one not-directly-work-related book a month, and only satisfied it in an amortized analysis; I am repeating the resolution this year. Since I only needed two posts to catalog the practical and philosophical articles on TheEGG, I will try something new with this one: a list and mini-review of the books I read last year to meet my resolution. I hope that based on this, you can suggest some books for me to read in 2015; or maybe my comments will help you choose your next book to read. I know that articles and blogs I’ve stumbled across have helped guide my selection. If you want to support TheEGG directly and help me select the books that I will read this year then consider donating something from TheEGG wishlist.

Cataloging a year of blogging: the philosophical turn

Passion and motivation are strange and confusing facets of being. Many things about them feel paradoxical. For example, I really enjoy writing, categorizing, and — obviously, if you’ve read many of the introductory paragraphs on TheEGG — blabbing on far too long about myself. So you’d expect that I would have been extremely motivated to write up this index of posts from the last year. Yet I procrastinated — although in a mildly structured way — on it for most of last week, and beat myself up all weekend trying to force words into this textbox. A rather unpleasant experience, although it did let me catch up on some Batman cartoons from my childhood. Since you’re reading this now, I’ve succeeded and received my hit of satisfaction, but the high variance in my motivation to write baffles me.

More fundamentally, there is the paradox of agency. It feels like my motivations and passions are aspects of my character, deeply personal and defining. Yet, it is naive to assume that they are determined by my ego; if I take a step back, I can see how my friends, colleagues, and even complete strangers push and pull the passions and motivations that push and pull me. For example, I feel like TheEGG largely reflects my deep-seated personal interests, but my thoughts do not come from me alone, they are shaped by my social milieu — or more dangerously by Pavlov’s buzzer of my stats page, each view and comment and +1 conditioning my tastes. Is the heavy presence of philosophical content because I am interested in philosophy, or am I interested in philosophy because that is what people want to read? That is the tension that bothers me, but it is clear that my more philosophical posts are much more popular than the practical. If we measure in terms of views then in 2014 new cancer-related posts accounted for only 4.7% of the traffic (with 15 posts), the more abstract cstheory perspective on evolution accounted for 6.6% (with 5 posts), while the posts I discuss below accounted for 57.4% (the missing chunk of unity went to 2014 views of post from 2012 and 2013). Maybe this is part of the reason why there was 24 philosophical posts, compared to the 20 practical posts I highlighted in the first part of this catalog.

Of course, this example is a little artificial, since although readership statistics are fun distraction, they are not particularly relevant just easy to quantify. Seeing the influence of the ideas I read is much more difficult. Although I think these exercises in categorization can help uncover them. In this post, I review the more philosophical posts from last year, breaking them down less autobiographically and more thematically: interfaces and useful delusions; philosophy of the Church-Turing thesis; Limits of science and dangers of mathematics; and personal reflections on philosophy and science. Let me know if you can find some coherent set of influences.

Cataloging a year of blogging: cancer and biology

Welcome to 111101111.

Another year has come to an end, and it is time to embrace tradition and reflect on the past twelve months. In fact, I will try to do one better and start a new tradition: cataloging a year of blogging.

Last year, I split up the 83 content heavy posts of 2013 into nine categories in three themes: established applications of evolutionary game theory (ethnocentrism and the public good; and mathematical oncology), expanding from behavior to society and mind (representations and rationality for replicators; feedback between finance & economics and ecology & evolution; and, learning, intelligence, and the social brain), and envisioning the algorithmic world (proof, automata, and physics; natural algorithms and biology; fitness landscapes and evolutionary equilibria; and, metamodeling and the (algorithmic) philosophy of science). In 2014 there was a sharp decrease in number of posts with only 44 articles of new content (and the 3 posts cataloging 2013, so 47 total) — this was due to a nearly 4 month blogging silence in the middle of the year — but a quarter increase in readership with 151,493 views compared to 2013’s 119,935 views. This time, I will need only two posts to survey the past year; this post for the practical and the next for the philosophical.

For me, the year was distributed between three cities, the usual suspects of Montreal and New York, and in October I moved down to Tampa, Florida to work with David Basanta and Jacob Scott in the Intergrated Mathematical Oncology department of the H. Lee Moffitt Cancer Center and Research Institute. A winter without snow is strange but wearing shorts in December makes up for it; plus the sunsets over the Gulf of Mexico are absolutely beautiful. Unsurprisingly, this move has meant that the practical aspects of my focus have shifted almost completely to biology; cancer, in particular.

This post is about the biology and oncology articles that made up about half of last year’s content. Given the autobiographical turn of this post, it will be (loosely) structured around three workshops that I attended in 2014, and the online conversations and collaborations that TheEGG was a host to.