• DocumentCode
    1763713
  • Title

    Hamiltonian Walks of Phylogenetic Treespaces

  • Author

    Gordon, Kevaughn ; Ford, Eric ; St.John, K.

  • Author_Institution
    Dept. of Math. & Comput. Sci., City Univ. of New York, New York, NY, USA
  • Volume
    10
  • Issue
    4
  • fYear
    2013
  • fDate
    July-Aug. 2013
  • Firstpage
    1076
  • Lastpage
    1079
  • Abstract
    We answer Bryant´s combinatorial challenge on minimal walks of phylogenetic treespace under the nearest-neighbor interchange (NNI) metric. We show that the shortest path through the NNI-treespace of n-leaf trees is Hamiltonian for all n. That is, there is a minimal path that visits all binary trees exactly once, under NNI moves.
  • Keywords
    bioinformatics; evolution (biological); genetics; genomics; trees (mathematics); Hamiltonian walks; NNI-treespace; binary trees; n-leaf trees; nearest-neighbor interchange metric; phylogenetic treespaces; Binary trees; Bioinformatics; Computational biology; Computer science; Measurement; Phylogeny; Silicon; Phylogenetic tree construction; analysis of algorithms; graph theory;
  • fLanguage
    English
  • Journal_Title
    Computational Biology and Bioinformatics, IEEE/ACM Transactions on
  • Publisher
    ieee
  • ISSN
    1545-5963
  • Type

    jour

  • DOI
    10.1109/TCBB.2013.105
  • Filename
    6587243
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1763713