Polynomial-Time Algorithms for Phylogenetic Inference Problems Involving Duplication and Reticulation

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
28 Downloads (Pure)

Abstract

A common problem in phylogenetics is to try to infer a species phylogeny from gene trees. We consider different variants of this problem. The first variant, called Unrestricted Minimal Episodes Inference, aims at inferring a species tree based on a model with speciation and duplication where duplications are clustered in duplication episodes. The goal is to minimize the number of such episodes. The second variant, Parental Hybridization, aims at inferring a species network based on a model with speciation and reticulation. The goal is to minimize the number of reticulation events. It is a variant of the well-studied Hybridization Number problem with a more generous view on which gene trees are consistent with a given species network. We show that these seemingly different problems are in fact closely related and can, surprisingly, both be solved in polynomial time, using a structure we call 'beaded trees'. However, we also show that methods based on these problems have to be used with care because the optimal species phylogenies always have a restricted form. To mitigate this problem, we introduce a new variant of Unrestricted Minimal Episodes Inference that minimizes the duplication episode depth. We prove that this new variant of the problem can also be solved in polynomial time.

Original languageEnglish
Article number8798653
Pages (from-to)14-26
Number of pages13
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume17
Issue number1
DOIs
Publication statusPublished - 2020

Keywords

  • duplication
  • gene trees
  • Hybridization Number problem
  • inference
  • Phylogenetics
  • polynomial-time algorithm

Fingerprint Dive into the research topics of 'Polynomial-Time Algorithms for Phylogenetic Inference Problems Involving Duplication and Reticulation'. Together they form a unique fingerprint.

Cite this