Polynomial-Time Algorithms for Phylogenetic Inference Problems

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
20 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 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.

Original languageEnglish
Title of host publicationAlgorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings
EditorsJesper Jansson, Carlos Martin-Vide, Miguel A. Vega-Rodriguez
Place of PublicationCham
PublisherSpringer
Pages37-49
Number of pages13
ISBN (Electronic)978-3-319-91938-6
ISBN (Print)978-3-319-91937-9
DOIs
Publication statusPublished - 2018
Event5th International Conference on Algorithms for Computational Biology, AlCoB 2018 - Hong Kong, China
Duration: 25 Jun 201826 Jun 2018
Conference number: 5
http://grammars.grlmc.com/AlCoB2018/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10849 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Conference on Algorithms for Computational Biology, AlCoB 2018
Abbreviated titleAlCoB 2018
CountryChina
CityHong Kong
Period25/06/1826/06/18
Internet address

Keywords

  • Phylogenetic inference problems
  • Polynomial-time algorithms

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

  • Cite this

    van Iersel, L., Janssen, R., Jones, M., Murakami, Y., & Zeh, N. (2018). Polynomial-Time Algorithms for Phylogenetic Inference Problems. In J. Jansson, C. Martin-Vide, & M. A. Vega-Rodriguez (Eds.), Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings (pp. 37-49). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10849 LNBI). Springer. https://doi.org/10.1007/978-3-319-91938-6_4