TreeSolve (portmanteau of “Tree” and “Resolve”) is a program for gene tree error-correction. By default, TreeSolve is designed for the error-correction of microbial gene trees (with horizontal gene transfer) but can be easily applied to non-microbial gene trees as well. TreeSolve takes as input a rooted gene tree topology, a known rooted species tree, and a collection of (unrooted) gene tree samples such bootstrap replicates or samples from a posterior distribution, and outputs an error-corrected gene tree topology. TreeSolve works by computing branch support values for the given rooted gene tree based on the given replicates/samples, collapsing weakly supported branches in the input gene tree, and then optimally resolving it based on both the input gene tree samples and the species tree while accounting for horizontal gene transfer, gene duplication, and gene loss. A key feature of TreeSolve is that it can output multiple distinct optimal resolutions, ordered by average branch support values. Further technical details and experimental evaluation appear in the paper cited below.
TreeSolve serves a similar purpose as the TreeFix-DTL program available from the software download page, but is much faster, far more scalable, and yields multiple candidate error-corrected gene trees (rather than just a single one).
TreeSolve was implemented by Misagh Kordi and is available open source under GNU GPL. Precompiled executables and a user manual are available below. Source code will be posted here shortly and can also be obtained by directly emailing Mukul Bansal at the email address provided below.
NOTE: It has been observed that TreeSolve sometimes crashes on some input instances. This happens due to excessive memory usage and typically occurs when the input gene trees are very large or highly unresolved. This is caused by an implementation oversight and a fixed version of TreeSolve is under development. Meanwhile, if users find TreeSolve crashing on their input files, they should be able to circumvent the memory issue by using the “-ts 5000” command line option.
This software can be cited as follows:
- TreeSolve: Rapid Error-Correction of Microbial Gene Trees
Misagh Kordi, Mukul S. Bansal.
Algorithms for Computational Biology (AlCoB) 2020, LNCS 12099: 125-139.
Funding: Development of the software resource(s) available from this webpage was funded in part by U.S. National Science Foundation awards MCB 1616514 and IES 1615573.