The prevalence of multifurcations in tree-space and their implications for tree-search

Simon Whelan, Daniel Money

    Research output: Contribution to journalArticlepeer-review

    51 Downloads (Pure)

    Abstract

    Phylogenetic tree-search is a major aspect of many evolutionary studies. Several tree rearrangement algorithms are available for tree-search, but it is hard to draw general conclusions about their relative performance because many effects are data set specific and can be highly dependent on individual implementations (e.g., RAxML or phyml). Using only the structure of the rearrangements proposed by the Nearest Neighbor Interchange (NNI) algorithm, we show tree-search can prematurely terminate if it encounters multifurcating trees. We validate the relevance of this result by demonstrating that in real data the majority of possible bifurcating trees potentially encountered during tree-search are actually multifurcations, which suggests NNI would be expected to perform poorly. We also show that the star-decomposition algorithm is a special case of two other popular tree-search algorithms, subtree pruning and regrafting (SPR) and tree bisection and reconnection (TBR), which means that these two algorithms can efficiently escape when they encounter multifurcations. We caution against the use of the NNI algorithm and for most applications we recommend the use of more robust tree-search algorithms, such as SPR and TBR. © 2010 The Author. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved.
    Original languageEnglish
    Pages (from-to)2674-2677
    Number of pages3
    JournalMolecular Biology and Evolution
    Volume27
    Issue number12
    DOIs
    Publication statusPublished - Dec 2010

    Keywords

    • algorithms
    • maximum likelihood
    • multifurcating trees
    • phylogenetic tree-search

    Fingerprint

    Dive into the research topics of 'The prevalence of multifurcations in tree-space and their implications for tree-search'. Together they form a unique fingerprint.

    Cite this