Some fun with evolutionary graph theory - and application to cancer?

For a few years now I've been interested in evolutionary graph theory - a branch of mathematics at the nexus of evolutionary dynamics and graph theory. To my knowledge this was all kicked off by Martin Nowak and colleagues with the 2005 Nature paper:  Evolutionary Dynamics on Graphs. One of the coolest results was that certain graph topologies exhibit striking changes in probabilities of fixation (assuming a Moran process) - particularly symmetric graphs called 'stars'.

A beautiful follow on paper by our friends at the Max Planck for evolutionary biology, led by +Arne Traulsen showed that this amplification of probability of selection led to a dramatic increase in time to fixation - sort of balancing out the advantage. You can read more about this in this terse paper in the Royal Society B entitled: The effect of population structure on the rate of evolution.

Since reading these two papers, I have given a fair amount of thought to this problem, but have not come to any sensible conclusions. +Alex Fletcher and +David Basanta and I spent a week or so once coming up with some code to think about how a cancer cell might invade an epithelial sheet (a biological structure that is topologically lattice-like). We never really figured out where to go from there (still working on it!!!), but in the mean time, conversations with Laura Hindersin and Benedikt Bauer at Max Planck about Laura's Phd work (example paper here: Almost all random graphs are amplifiers of selection for birth-death processes, but suppressors of selection for death-birth processes) has sparked a lot of interesting thought and conversation.

Further, at the recent conference: Cancer Evolution Through Space and Time the conversation continued and we started talking more about 'mixed' topology structures. The conversation has continued on twitter, culminating with a new student in my lab +Sudhir Manickavel starting some work simulating evolution. Here's where our thinking is going:

Twitter crowdsource #graphtheory problem. [assuming a Moran process] pic.twitter.com/h5e6LLDasU

— Jacob G Scott (@CancerConnector) September 30, 2015

@CancerConnector @EvolTheoArne @dbasanta @ara_anderson The "ring" can't decide where it belongs... ;) pic.twitter.com/dZn9dSjDNv

— Benedikt Bauer (@EvolTheoBene) October 19, 2015

@EvolTheoBene why not proper mixed topology? (Plus/minus green edges-pardon white board #clinicday @LauraHindersin pic.twitter.com/1V1diJkzC7

— Jacob G Scott (@CancerConnector) October 19, 2015

@CancerConnector @EvolTheoArne @ara_anderson @dbasanta Nice idea, this is what the rank in fix prob looks like pic.twitter.com/pEW7rC4s5o

— Benedikt Bauer (@EvolTheoBene) October 22, 2015

Building his first adjacency matrix - new volunteer to Theory Division! #mathonco pic.twitter.com/CRlYuQSIet

— Jacob G Scott (@CancerConnector) October 16, 2015

When he first started considering this project +Sudhir Manickavel , a medical student asked of the Royal Society paper mentioned above:

"I read the paper and I found it interesting, especially the idea that even though star structured populations have a greater fixation probability it actually takes them longer to fix.

I do have one question about the paper, in reference to a tumor how would you define a tumor population as well mixed or star structured?" 

A great question...  to which I responded:

"What is the topology of an epithelial sheet? What is the topology of a colonic crypt?  Does the topology of the stem cell niche within the crypt differ from that of the walls of the crypt?  How would you characterize the topology of bone marrow? Or - in infectious diasese: Of a blood borne pathogen? Of a biofilm?"

And included a link to a Gatenby classic which opens with:

"The human body plays with evolutionary fire" and discusses the unique (changing) topology of the colonic crypt and how this may influece evolutionary dynamics...

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3744108/

Which seemed to sell him on the topic as just this morning, I looked in my dropbox, and it looks like +Sudhir Manickavel is making some progress (though there seems to be a missing node...  :) ):

initial condition plotted with networkx to study the moran process evolving on a 'mixed' topology structure... is it a ring or is it a star?

Anyways, the start of a fun project either way.