Persistent homology applied to evolution and Twitter

In this post I’ll let you know about an application and a variation of persistent homology I learnt about at the Young Topologists Meeting 2015. You might want to read my post on persistent homology first!

In his talks Gunnar Carlsson (Stanford) gave lots of examples of applications of persistent homology. A really interesting one for me was applying persistent homology to evolution trees. Remember that homology tells us about the shape of the data, and in particular if there are any holes or loops in it. We tend to think of evolution as a tree:

Tree of life

but in reality the reason why all our models for evolution are trees is that we take the data and try to fit it to the best tree we can. We don’t even think that it might have a different shape!

In reality, as well as vertical evolution, where one species becomes another, or two other, distinct species over time, we have something called horizontal  or reticulate evolution. This is where two species combine to form a hybrid species. In their paper Topology of viral evolution, Chan, Carlsson and Rabadan show how the homology (think of this as something describing the shape of the data, specifically the holes or loops that appear) of trees may be different if we take into account species merging together:

Figure from http://www.pnas.org/content/110/46/18566.full
Figure from http://www.pnas.org/content/110/46/18566.full

They go on to show how persistent homology can detect such loops caused by horizontal evolution, in the example of viral evolution. This is a brand new approach and really exciting as we now have a way of finding out how many loops are in a given evolutionary dataset, and which data points they correspond to. This can tell us about horizontal evolution, as well as vertical!

Up next is work from Balchin and Pillin (University of Leicester) on a variation of persistent homology inspired by directed graphs. The images in this section are from the slides of Scott Balchin’s talk at the young topologists meeting! The motivation for their variation is: what if you don’t simply have data points, but some other information as well. Take this example of people following people on twitter: draw an arrow from person A to person B if person A follows person B.

Twitter example

We see that Andy follows Cara but Cara does not reciprocate! If you just had Andy and Cara connected by an edge then this information would be lost. Balchin and Pillin looked at a way of encoding this extra information into the complex, taking into account the number of arrows you would need to move along to get from Andy to Cara (1) and also from Cara to Andy (2, via Bill). I will post a link to their paper here as soon as it is released. When the data is considered without this extra information, persistent homology gives a (crazy) barcode that looks like this:

Barcode

but when you include the directions you get a slightly less mysterious bar code:

Barcode

which is in a lot of ways more accurate and easy to interpret.

Balchin gave another example of a system where direction mattered: non-transitive dice. If you have a few 6 sided dice, you can represent each one by a circle with 6 numbers in it: the numbers on the sides of the dice! Then put an arrow from dice A to dice B if dice A beats dice B on average.

Dice

The non-transitive means sometimes there are loops where dice A beats dice B which beats dice C, but then dice C beats dice A! You can actually buy non-transitive dice and play with them in real life. As you can probably tell, the arrows in this picture are important and so we want to make sure we don’t loose the directions when considering the homology!

There are a few more applications of persistent homology I would like to share with you and hopefully I will get the chance some other week!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s