Computer Sciences Colloquium - Phylogenetic questions inspired by the theorems of Arrow and Dilworth

Mike Steel, University of Canterbury, New Zealand

17 June 2018, 11:00 
Schreiber Building, Room 006 
Computer Sciences Colloquium


Biologists frequently need to reconcile conflicting estimates of the evolutionary relationships between species by taking a ‘consensus’ of a set of phylogenetic trees. This is because different data and/or different methods can produce different trees. If we think of each tree as providing a ‘vote’ for the unknown true phylogeny, then we can view consensus methods as a type of voting procedure. Kenneth Arrow’s celebrated ‘impossibility theorem’ (1950) shows that no voting procedure can simultaneously satisfy seemingly innocent and desirable properties. We consider a similar axiomatic approach to consensus and asks what properties can be jointly achieved.


In the second part of the talk, we consider phylogenetic networks (which are more general than trees as they allow for reticulate evolution).  The question ‘when is a phylogenetic network merely a tree with additional links between its edges?’ is relevant to biology and interesting mathematically.   It has recently been shown that such ‘tree-based’ networks can be efficiently characterized.  We  describe some further results related to Dilworth’s theorem for posets (1950), and matching theory in bipartite graphs.  In this way, one can obtain fast algorithms for determining when a network is tree-based and, if not, to calculate how ‘close’ to tree-based it is.



Michael A. Steel is a New Zealand mathematician and statistician, a professor of mathematics and statistics and the director of the Biomathematics Research Centre at the University of Canterbury in Christchurch, New Zealand. He is known for his research on modeling and reconstructing evolutionary trees.


He won the Hamilton Memorial Prize of the Royal Society of New Zealand in 1994; this prize is given annually to a New Zealand mathematician for work done within five years of a Ph.D.

In 1999 he won the research award of the New Zealand Mathematical Society "for his fundamental contributions to the mathematical understanding of phylogeny, demonstrating a capacity for hard creative work in combinatorics and statistics and an excellent understanding of the biological implications of his results."


In 2018, he was elected as a Fellow of the International Society for Computational Biology, for his outstanding contributions to the fields of computational biology and bioinformatics.

Tel Aviv University, P.O. Box 39040, Tel Aviv 6997801, Israel
UI/UX Basch_Interactive