Challenges

Phylogenetics: Challenges and conjectures from the INI programme 2007.

List of challenges and conjectures (PDF, 90.3 KB)
Final Report (PDF, 164 KB) for the 'Phylogenetics' Programme
 

$100 Challenges

Summer in Fiordland - without
the sandflies. James Shanks
enjoying a walk in the Park,
Dec. 2000.
Summer in Fiordland

(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]
  • 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.