Inferring optimal species trees under gene duplication and loss

M. S. Bayzid, S. Mirarab, T. Warnow

Research output: Contribution to journalConference article

Abstract

Species tree estimation from multiple markers is complicated by the fact that gene trees can differ from each other (and from the true species tree) due to several biological processes, one of which is gene duplication and loss. Local search heuristics for two NP-hard optimization problems - minimize gene duplications (MGD) and minimize gene duplications and losses (MGDL) - are popular techniques for estimating species trees in the presence of gene duplication and loss. In this paper, we present an alternative approach to solving MGD and MGDL from rooted gene trees. First, we characterize each tree in terms of its "subtree-bipartitions" (a concept we introduce). Then we show that the MGD species tree is defined by a maximum weight clique in a vertex-weighted graph that can be computed from the subtree-bipartitions of the input gene trees, and the MGDL species tree is defined by a minimum weight clique in a similarly constructed graph. We also show that these optimal cliques can be found in polynomial time in the number of vertices of the graph using a dynamic programming algorithm (similar to that of Hallett and Lagergren(1)), because of the special structure of the graphs. Finally, we show that a constrained version of these problems, where the subtree-bipartitions of the species tree are drawn from the subtree-bipartitions of the input gene trees, can be solved in time that is polynomial in the number of gene trees and taxa. We have implemented our dynamic programming algorithm in a publicly available software tool, available at http://www.cs.utexas.edu/users/phylo/software/dynadup/.

Original languageEnglish (US)
Pages (from-to)250-261
Number of pages12
JournalPacific Symposium on Biocomputing
StatePublished - Jan 1 2013
Externally publishedYes
Event18th Pacific Symposium on Biocomputing, PSB 2013 - Kohala Coast, United States
Duration: Jan 3 2013Jan 7 2013

Keywords

  • Clique
  • Gene duplication and loss
  • Incomplete lineage sorting

ASJC Scopus subject areas

  • Biomedical Engineering
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Inferring optimal species trees under gene duplication and loss'. Together they form a unique fingerprint.

  • Cite this