Trees of life – for instance showing how animals evolved from a common ancestor – are centrepieces of modern biology. However, constructing and reasoning about such evolutionary trees is more complex than it might at first seem. “In recent years we’ve begun to realize that there isn’t really one tree of life. Depending on where you look, and the methods you use to build the tree, you get different outcomes”, Dr. Steven Kelk says.

Computer says no

Make no mistake: Dr. Kelk is a mathematician rather than a biologist. Where does his fascination for evolutionary trees come from? “To understand what’s happening with two different trees, you first want to try and put a number on their dissimilarity. While there are multiple ways to define this distance, some of the more interesting distances are really challenging to compute. I’m particularly interested in cases where you currently can’t calculate the distance, because the trees are simply too big for the algorithm to handle.”

The mathematical answer to this problem lies in something called kernelization. In this case, it’s about reducing the size of the evolutionary trees without losing information. You can then use the compacted trees, which pose a much smaller challenge to computers – provided that you know how to shrink them. That’s where rigorous mathematics comes in.

Dr. Kelk: “A long time ago, others proved you could reduce the size of two evolutionary trees to a multiple of their dissimilarities: specifically, their size will be at most 28 multiplied by their distance. That’s a mathematically guaranteed outcome, and it means that huge trees which are in fact not so different, become extremely small after this reduction. In addition to shrinking the trees before letting a computer do calculations, it also tells you something about the evolutionary trees themselves.”

The topic has since fascinated him. Together with co-authors, Dr. Kelk provided the mathematical recipes to shrink pairs of evolutionary trees even further. “Recently, we found out how to go down from a factor of 28 to a factor of 15. From there, we went down to a factor of 11 – and that’s where we are now. But what is the limit? And what would new reduction rules look like?”

Launching the systematic search

Thanks to the NWO KLEIN-1 grant for a total of €267k, Dr. Kelk can continue his quest for ever-smaller trees of life. “For me, the excitement is about seeing how low you can go. Can you develop new general theories which help you do that in the process? It would be beautiful to systematize this search: you try and develop a new type of math to structure it, and to move beyond an ad hoc, case-based search and analysis.”

Through mathematics, increasingly compact evolutionary trees can then contribute to a growing understanding of the evolution of life.

Read more:

• DKE research theme: Algorithms, Complexity, and Optimization (ALGOPT)

Home page image: "Day 9 - Fossilized Root System" by akhenatenator