Challenges
Phylogenetics: Challenges and conjectures from the INI programme 2007.
List of challenges and conjectures (PDF, 167 KB)
Final Report (PDF, 164 KB) for the 'Phylogenetics' Programme
$100 Challenges
 |
(Conditions: A choice of NZ$100 plus bottle of NZ wine, OR US$100, OR free registration and accommodation grant at the annual New Zealand phylogenetics meeting (value NZ$300 - flights not included!) for the first correct solution to any of these problems).
- The triplet cover conjecture:
Answer the following question stated at the end of Dress et al. (J. Math. Biol. 65: 77-105) 2012), and posed at the 'Gryphylo' conference (Greifswald, July 2014) (100 Euro prize):
Q1. Does there exist a triplet cover of a binary tree that is not a strong lasso?
- [Update: July 22, 2014: A proof that no such cover exists has been proposed by Stefan Gruenewald]
- [Update May 31, 2018: The paper by Gruenewald et al that includes a proof that no such triplet cover exists has now been published.
Grunewald, S., Huber, K. T., Moulton, V., and Steel, M. Combinatorial properties of triplet covers for binary trees. Adv. Appl. Math. 99: 59-82] - The phylogenetic inadmissibility conjectures (PDF, 34.4 KB)
- The parsimony conjectures (I and II) (PDF, 13.9 KB)
- [24 November. 2009] Solved! A constructive proof of the conjecture in MP1 has been submitted by Elizabeth Housworth and Juanjuan Chai (Indiana University).
- [19 August, 2010] Prize sent to Juanjuan Chai; a preprint of their paper, to appear in Bull. Math. Biology, can be read here. - The SPR conjecture (PDF, 11.1 KB)
- [UPDATE: July 2010] Stefan Gruenewald, presented an outline proof at Kaikoura09, then found an error in the argument -- he has a possible counterexample but it will require a computer to verify.
- This has now been solved for rooted binary trees by Charles Semple and Magnus Bordewich in Feb. 2004
- [25 July, 2006] A claimed solution was submitted by researchers in Canada -- however [1 September,2006] the author informed us that there was an error in the argument
- [UPDATE: 5 August 2016] The conjecture appears to be proved in this 2015 ArXiv submission by Whidden and Matsen: http://arxiv.org/abs/1511.07529. - My favourite conjecture (PDF, 20 KB)
- This has been solved for 'balanced' trees by Elchannan Mossel, Nov. 2001
- [1 Sept. 2005] Mossel et al. have claimed a solution for the general case.
- [22 Sept. 2005] Solved! Mossel, Roch and Daskalakis presented with prize at UC Berkeley for their clever proof of this conjecture. You can read about it in this paper (ucdavis.edu). - Followup $100 conjecture: In reference to the previous conjecture (and its solution) show that a sequence length growth of strictly greater than
log(n) is needed for tree reconstruction if one is restricted to using pairwise sequence comparisons (eg `distances').
- [1 Oct. 2009] Solved! Sebastien Roch (UCLA) showed log(n) suffices even for distances, leading to a paper in the journal Science 327(5971):1376 - 1379, 2010. Prize offered. - The quartet challenge: Is the following problem NP-hard? Given a binary phylogenetic X--tree T and a collection Q of quartet subtrees on X, is T the only tree that displays Q?
- [UPDATE: 1 Dec. 2010] A proof that the problem is NP-hard has just been posted on Arxiv by Habib and Stacho.
- [UPDATE: 15 Jan. 2011] Independently, an alternative proof that the problem is ASP-complete (and hence NP-complete) has been posted on Arxiv by Bonet, Linz and St-John.
- [UPDATE: 20 Jun. 2011] $100 presented to Linz et al. at Isaac Newton Institute, Cambridge UK, after delivery of their paper.
- [UPDATE: 26 May. 2012] $100 received via courier by Juraj Stacho for his solution with Michel Habib, presented at CPM 2011, and since submitted to a journal.
