Walks in phylogenetic treespace

详细信息    查看全文

• 作者：Alan Joseph J. Caceres¹ ; ² ; ^a ; Samantha Daley¹ ; ² ; ^a ; John DeJesus¹ ; ² ; ^a ; Michael Hintze¹ ; ² ; ^a ; Diquan Moore¹ ; ² ; ^a ; Katherine St. John ; ¹ ; ^a ; ^{stjohn@lehman.cuny.edu}
• 关键词：Graph algorithms ; Computational biology ; Tree metrics ; Phylogenetics
• 刊名：Information Processing Letters
• 出版年：2011
• 出版时间：15 June 2011
• 年：2011
• 卷：111
• 期：12
• 页码：600-604
• 全文大小：163 K

文摘

We prove that the spaces of unrooted phylogenetic trees are Hamiltonian for two popular search metrics: Subtree Prune and Regraft (SPR) and Tree Bisection and Reconnection (TBR). Further, we make progress on two conjectures of Bryant on searching phylogenetic treespace: treespace under the Nearest Neighbor Interchange (NNI) metric has a 2-walk, and there exist SPR neighborhoods without complete NNI walks.