Department of Mathematics and Computer Science, Lehman College-City University of New York, 250 Bedford Park Boulevard West, Bronx, NY 10468, USA.
IEEE/ACM Trans Comput Biol Bioinform. 2013 Jan-Feb;10(1):236-9. doi: 10.1109/TCBB.2012.136.
A nearest-neighbor-interchange (NNI)-walk is a sequence of unrooted phylogenetic trees, T1, T2, . . . , T(k) where each consecutive pair of trees differs by a single NNI move. We give tight bounds on the length of the shortest NNI-walks that visit all trees in a subtree-prune-and-regraft (SPR) neighborhood of a given tree. For any unrooted, binary tree, T, on n leaves, the shortest walk takes Θ(n²) additional steps more than the number of trees in the SPR neighborhood. This answers Bryant’s Second Combinatorial Challenge from the Phylogenetics Challenges List, the Isaac Newton Institute, 2011, and the Penny Ante Problem List, 2009.
最近邻交换（NNI）-游走是一系列无根系统发育树，T1、T2、……、T(k)，其中每对连续的树通过单个 NNI 移动来区分。我们对访问给定树的子树剪枝和重接（SPR）邻域中的所有树的最短 NNI-游走的长度给出了严格的界限。对于任何具有 n 个叶子的无根二叉树 T，最短的游走比 SPR 邻域中的树的数量多Θ(n²)个额外的步骤。这回答了 2011 年的系统发育学挑战赛列表、艾萨克·牛顿学院和 2009 年的 Penny Ante 问题列表中 Bryant 的第二个组合挑战。
Zotero 插件