Polynomial-time algorithms for phylogenetic inference problems

DOI10.1007/978-3-319-91938-6_4MaRDI QIDQ1660113zbMATH OpenOpenAlexFDO

Authors Y. Aharonov

Publication date 15 August 2018

Full work available at URL https://arxiv.org/abs/1802.00317, http://resolver.tudelft.nl/uuid:43e555b0-8999-4fa1-8476-7c8e854b27b8

zbMATH Keywords

polynomial-time algorithmsphylogenetic inference problems

Mathematics Subject Classification ID

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

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

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

Cited in

(10)

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

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)