Penny Ante
Combinatorial Challenge I: Walking through trees
- Submitted by David Bryant
An "NNI-walk" is a sequence T1, T2, ... , Tk of unrooted binary phylogenetic trees where each consecutive pair of trees differ by a single NNI.
i. [Question] What is the shortest NNI walk that passes through all binary trees on n leaves?
ii. [Question] Suppose we are given a tree T. What is the shortest NNI walk that passes through all the trees that lie at most one SPR (subtree prune and regraft) move from T?
