Discrete time trees: theory and open problems

Alex Gavryushkin

Joint work with:
• Chris Whidden, Fred Hutchinson Cancer Research Center, Seattle, WA, USA
• Erick Matsen, FHCRC, U. of Washington, Seattle, WA, USA
• Alexei Drummond, U. of Auckland, NZ

November 15, 2016

Why is this important?

• Tree search algorithms
• Model testing/selection and other simulation studies

Trees are many!

Main idea

(my failed proof)

History of the NNI graph

• Over 25 year of work!
• Over 7 erroneous papers published!

What's wrong with the NNI graph?

1. The Split Theorem

2. The merge and sort trick

RNNI is free from all these!

• Split theorem. Tick.
• Merge and sort doesn't work. Tick
• Efficient polynomial algorithm?

What is an approximate (?) algorithm

$\frac{1}{2} \log_3 \frac{(n-1)!n!}{6^{n-1}} \leq \mathrm{Diam} \leq n^2 - 3n - \frac{5}{8}$

What we've done?

• Introduced the RNNI graph on ranked trees (to the best of our knowledge)

• Established basic geometric properties of the graph

• Designed an efficient approximate algorithm for computing shortest paths

• Proved that all the fancy NNI methods, e.g. Sleator-Tarjan-Thurston and merge-and-sort argument, don't work

• Failed to prove that RNNI is NP-hard

What has to be done?

• Is RNNI polynomial? Complexity?
• Split Theorem
• Are these two related?
• ...

Hence, time trees are (more or less) fine

Looks like a problem

[Stadler, JTB 2010]  must be cheating then :)

But then we can cheat a bit too!

... and introduce imaginary nodes

References:

• Sleator, Tarjan, and Thurston. Short Encodings of Evolving Structures. (1992)
• Dasgupta, He, Jiang, Li, Tromp, and Zhang. On Computing the Nearest Neighbor Interchange Distance. (1999)
• Stadler. Sampling-through-time in birthâ€“death trees. (2010)
• Gavryushkin and Drummond. The space of ultrametric phylogenetic trees. (2015)
• Gavryushkin, Whidden, and Matsen. The combinatorics of discrete time trees: theory and open problems. (bioRxiv, 2016)