Polynomial-Time Algorithms for Phylogenetic Inference Problems

Conference paper (2018)

Authors

L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS
R. Janssen Discrete Mathematics and Optimization - EEMCS
M.E.L. Jones Discrete Mathematics and Optimization - EEMCS
Yukihiro Murakami Discrete Mathematics and Optimization - EEMCS
Norbert Zeh Dalhousie University
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2018 L.J.J. van Iersel, R. Janssen, M.E.L. Jones, Yukihiro Murakami, Norbert Zeh
DOI: https://doi.org/10.1007/978-3-319-91938-6_4
Phylogenetic inference problems Polynomial-time algorithms
More Info
expand_more

Published Date

2018

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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 of 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 of 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 some restricted form. We discuss several possibilities to overcome this problem.