Polynomial-time algorithms for phylogenetic inference problems

DOI10.1007/978-3-319-91938-6_4zbMATH Open1392.92065arXiv1802.00317OpenAlexW2963793240MaRDI QIDQ1660113FDOQ1660113

Authors: Y. Aharonov 

Publication date: 15 August 2018

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 emph{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

Full work available at URL: https://arxiv.org/abs/1802.00317

Recommendations

• Phylogenetic Networks: Properties and Relationship to Trees and Clusters
• Computational Science – ICCS 2005
• From Gene Trees to Species Trees
• Algorithms for phylogeny reconstruction in a new mathematical model
• Tree Compatibility and Inferring Evolutionary History

zbMATH Keywords

polynomial-time algorithmsphylogenetic inference problems

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms (68W40)

Cited In (10)

• Research in Computational Molecular Biology
• Incomplete directed perfect phylogeny in linear time
• Optimal Completion of Incomplete Gene Trees in Polynomial Time Using OCTAL
• Autopolyploidy, allopolyploidy, and phylogenetic networks with horizontal arcs
• Approximation algorithms for the fixed-topology phylogenetic number problem
• Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances
• Conflict Resolution Algorithms for Deep Coalescence Phylogenetic Networks.
• High-performance algorithm engineering for computational phylogenetics
• Evolutionary trees can be learned in polynomial time in the two-state general Markov model
• The rigid hybrid number for two phylogenetic trees

This page was built for publication: Polynomial-time algorithms for phylogenetic inference problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1660113)