Phylogenetic Tree Search Using Custom Optimality Criteria

Search for phylogenetic trees that are optimal using a user-defined criterion. Contains a "shiny" user interface for interactive tree search and exploration of results, including character visualization, rogue taxon detection, tree space mapping, and cluster consensus trees. Handles inapplicable data using the algorithm of Brazeau, Guillerme and Smith (2019) using the "Morphy" library. Implements Profile Parsimony (Faith and Trueman, 2001) , and Successive Approximations (Farris, 1969) .

Build Status codecov CRAN Status Badge CRAN Downloads Project Status: Active – – The project has reached a stable, usable state and is being actively developed. This package exists to allow parsimony-style tree searches in R.

It extends the basic functionality available in phangorn, with a view to making tree search faster and more efficient, and allowing user-defined optimality criteria to be employed.

Implied weighting and heuristic searches such as the Parsimony Ratchet are implemented (function: Ratchet). Browse the vignettes (with vignette(package = "TreeSearch") to get started.


Install and load the library from CRAN as follows:


If you're feeling brave, you can install the development version thus:

if(!require(devtools)) install.packages("devtools")

Optimailty criteria

TreeSearch allows the implementation of various optimality criteria, including

  • The Profile Parsimony approach introduced by Faith and Trueman (2001).
  • Successive Approximations weighting (Farris 1969).
  • Fitch parsimony with inapplicable data (Brazeau, Guillerme and Smith, 2017).

It is also possible to specify bespoke optimality criteria.


Brazeau, M. D., Guillerme, T. and Smith, M. R. 2017. Morphological phylogenetic analysis with inapplicable data. BioRχiv. doi:10.1101/209775

D. P. Faith, J. W. H. Trueman, Towards an inclusive philosophy for phylogenetic inference. Syst. Biol. 50, 331–350 (2001). doi:10.1080/10635150118627

Farris, J. S. (1969). A successive approximations approach to character weighting. Systematic Biology, 18(4), 374–385. doi:10.2307/2412182


TreeSearch 0.3.0

New features

  • Implement an information theoretic tree distance measure (Smith, in prep)
  • Prepare for new random number generator in R3.6.0


  • Function TreeSplits is deprecated; use Tree2Splits instead.

Bug fixes

  • Correct some mistakes in the documentation

TreeSearch 0.2.2

Bug fixes

  • Correct vignette titles

TreeSearch 0.2.1

New features

  • CollapseNodes and CollapseEdges allow the creation of polytomies
  • Tree2Splits lists the bipartition splits implied by a tree topology


  • SplitFrequency now supports larger trees
  • Can specify tip labels directly to ReadTntTree, to avoid reliance on generative file

Bug fixes

  • Export missing functions

TreeSearch 0.2.0

New features

  • RootTree function allows rooting of tree on incompletely specified or single-taxon outgroup
  • AllTBR returns all trees one TBR rearrangement away
  • TBRMoves reports all possible TBR rearrangements
  • Jackknife conducts Jackknife resampling
  • SplitFrequency reports frequency of clades in a forest
  • SupportColour allows visual marking of support values
  • ApeTime reports the creation date of an ape-exported tree
  • SortTree flips nodes into a consistent left-right order
  • AsBinary supports 0


  • [IW]RatchetConsensus renamed to [IW]MultiRatchet, giving a better description of the function's purpose
  • Don't warn about missing EOL when reading Nexus or TNT files
  • Add new 12-colour colourblind-friendly palette
  • FitchSteps now supports datasets with tips not found in tree
  • Improve portability of function ReadTntTree

Bug fixes

  • [IW]MultiRatchet now considers trees identical even if they've been hit a different number of times

TreeSearch 0.1.2

Bug fixes

  • Update MorphyLib library to fix C warnings
  • Remove non-ASCII characters from data
  • Disable slow-building and problematic vignette
  • Use local copy of citation style when building vignettes

TreeSearch 0.1.0

New features

  • Helper functions to read Nexus and TNT data and trees.
  • Brewer palette in local data to allow easier colouring


  • Allow additional parameters to be passed to consensus via ConsensusWithout

Bug fixes

  • C11 compliance
  • IWRatchetConsensus now relays concavity value to subsequent functions
  • ReadCharacters returns labels for all characters and states if character_num = NULL

TreeSearch 0.0.8

New features

  • Added NJTree function as shortcut to generate Neighbour-Joining tree from a dataset
  • Add functions to allow recovery of all trees one rearrangement from that input

Efficiency gains

  • Separate out NNISwap functions to allow more efficient rearrangement of edgeLists
  • [9002] Improve efficiency by using three-pass algorithm in place of four-pass precursor
  • [9004] Bootstrap search improvements

Bug fixes

  • [9003] User now able to specify value of concavity constant (was overridden to k = 4)
  • [9003] Bootstrap replicates now scored correctly (and without warning) under implied weights

TreeSearch 0.0.7


  • Integrated with this package (previously in inapplicable)
  • Handle inapplicable data via API to Martin Brazeau's Morphy Phylogenetic Library

Profile Parsimony:

  • Integrated with this package (previously in ProfileParsimony)
  • Faster calculation of concavity profiles in C
  • Persistent memoization with R.cache

TreeSearch 0.0.6

  • First CRAN submission

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.


1.0.1 by Martin R. Smith, a month ago,

Report a bug at

Browse source code at

Authors: Martin R. Smith [aut, cre, cph] , Martin Brazeau [cph]

Documentation:   PDF Manual  

GPL (>= 3) license

Imports ape, cli, cluster, fastmatch, future, phangorn, promises, protoclust, Rcpp, Rdpack, Rogue, shiny, shinyjs, stats, TreeDist, TreeTools

Suggests knitr, rmarkdown, Quartet, testthat, vdiffr

Linking to Rcpp, TreeTools

System requirements: C++14

Suggested by CongreveLamsdell2016, TreeDist.

See at CRAN