Non-parametric correction of estimated gene trees using TRACTION

Sarah Christensen, Erin K. Molloy, Pranjal Vachaspati, Ananya Yammanuru, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

Motivation: Estimated gene trees are often inaccurate, due to insufficient phylogenetic signal in the single gene alignment, among other causes. Gene tree correction aims to improve the accuracy of an estimated gene tree by using computational techniques along with auxiliary information, such as a reference species tree or sequencing data. However, gene trees and species trees can differ as a result of gene duplication and loss (GDL), incomplete lineage sorting (ILS), and other biological processes. Thus gene tree correction methods need to take estimation error as well as gene tree heterogeneity into account. Many prior gene tree correction methods have been developed for the case where GDL is present. Results: Here, we study the problem of gene tree correction where gene tree heterogeneity is instead due to ILS and/or HGT. We introduce TRACTION, a simple polynomial time method that provably finds an optimal solution to the RF-optimal tree refinement and completion (RF-OTRC) Problem, which seeks a refinement and completion of a singly-labeled gene tree with respect to a given singly-labeled species tree so as to minimize the Robinson-Foulds (RF) distance. Our extensive simulation study on 68,000 estimated gene trees shows that TRACTION matches or improves on the accuracy of well-established methods from the GDL literature when HGT and ILS are both present, and ties for best under the ILS-only conditions. Furthermore, TRACTION ties for fastest on these datasets. We also show that a naive generalization of the RF-OTRC problem to multi-labeled trees is possible, but can produce misleading results where gene tree heterogeneity is due to GDL.

Original languageEnglish (US)
Article number1
JournalAlgorithms for Molecular Biology
Volume15
Issue number1
DOIs
StatePublished - Jan 4 2020

Keywords

  • Gene tree correction
  • Horizontal gene transfer
  • Incomplete lineage sorting

ASJC Scopus subject areas

  • Structural Biology
  • Molecular Biology
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Non-parametric correction of estimated gene trees using TRACTION'. Together they form a unique fingerprint.

  • Datasets

    Data from TRACTION: Fast non-parametric improvement of estimated gene trees

    Christensen, S. (Creator), Molloy, E. K. (Creator), Vachaspati, P. (Creator) & Warnow, T. (Creator), University of Illinois at Urbana-Champaign, Jul 29 2019

    Dataset

    Cite this