Polynomial-Time Algorithms for Phylogenetic Inference Problems

Leo van Iersel; Remie Janssen; Mark Jones; Yukihiro Murakami; Norbert Zeh

doi:10.1007/978-3-319-91938-6_4

Polynomial-Time Algorithms for Phylogenetic Inference Problems

Leo van Iersel^*, Remie Janssen, Mark Jones, Yukihiro Murakami, Norbert Zeh

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

4 Citations (Scopus)

72 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 language	English
Title of host publication	Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings
Editors	Jesper Jansson, Carlos Martin-Vide, Miguel A. Vega-Rodriguez
Place of Publication	Cham
Publisher	Springer
Pages	37-49
Number of pages	13
ISBN (Electronic)	978-3-319-91938-6
ISBN (Print)	978-3-319-91937-9
DOIs	https://doi.org/10.1007/978-3-319-91938-6_4
Publication status	Published - 2018
Event	5th International Conference on Algorithms for Computational Biology, AlCoB 2018 - Hong Kong, China Duration: 25 Jun 2018 → 26 Jun 2018 Conference number: 5 http://grammars.grlmc.com/AlCoB2018/

Publication series

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

Conference

Conference	5th International Conference on Algorithms for Computational Biology, AlCoB 2018
Abbreviated title	AlCoB 2018
Country/Territory	China
City	Hong Kong
Period	25/06/18 → 26/06/18
Internet address	http://grammars.grlmc.com/AlCoB2018/

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Phylogenetic inference problems
Polynomial-time algorithms

Access to Document

10.1007/978-3-319-91938-6_4

10.1007_978-3-319-91938-6_4Final published version, 384 KB

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

van Iersel, Leo ; Janssen, Remie ; Jones, Mark et al. / Polynomial-Time Algorithms for Phylogenetic Inference Problems. Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings. editor / Jesper Jansson ; Carlos Martin-Vide ; Miguel A. Vega-Rodriguez. Cham : Springer, 2018. pp. 37-49 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{43e555b089994fa184767c8e854b27b8,

title = "Polynomial-Time Algorithms for Phylogenetic Inference Problems",

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.",

keywords = "Phylogenetic inference problems, Polynomial-time algorithms",

author = "{van Iersel}, Leo and Remie Janssen and Mark Jones and Yukihiro Murakami and Norbert Zeh",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. ; 5th International Conference on Algorithms for Computational Biology, AlCoB 2018, AlCoB 2018 ; Conference date: 25-06-2018 Through 26-06-2018",

year = "2018",

doi = "10.1007/978-3-319-91938-6_4",

language = "English",

isbn = "978-3-319-91937-9",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "37--49",

editor = "Jesper Jansson and Carlos Martin-Vide and Vega-Rodriguez, {Miguel A.}",

booktitle = "Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings",

url = "http://grammars.grlmc.com/AlCoB2018/",

}

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 & MA Vega-Rodriguez (eds), Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10849 LNBI, Springer, Cham, pp. 37-49, 5th International Conference on Algorithms for Computational Biology, AlCoB 2018, Hong Kong, China, 25/06/18. https://doi.org/10.1007/978-3-319-91938-6_4

Polynomial-Time Algorithms for Phylogenetic Inference Problems. / van Iersel, Leo; Janssen, Remie; Jones, Mark et al.
Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings. ed. / Jesper Jansson; Carlos Martin-Vide; Miguel A. Vega-Rodriguez. Cham: Springer, 2018. p. 37-49 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10849 LNBI).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Polynomial-Time Algorithms for Phylogenetic Inference Problems

AU - van Iersel, Leo

AU - Janssen, Remie

AU - Jones, Mark

AU - Murakami, Yukihiro

AU - Zeh, Norbert

N1 - Conference code: 5

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Phylogenetic inference problems

KW - Polynomial-time algorithms

UR - http://www.scopus.com/inward/record.url?scp=85049171736&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-91938-6_4

DO - 10.1007/978-3-319-91938-6_4

M3 - Conference contribution

AN - SCOPUS:85049171736

SN - 978-3-319-91937-9

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 37

EP - 49

BT - Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings

A2 - Jansson, Jesper

A2 - Martin-Vide, Carlos

A2 - Vega-Rodriguez, Miguel A.

PB - Springer

CY - Cham

T2 - 5th International Conference on Algorithms for Computational Biology, AlCoB 2018

Y2 - 25 June 2018 through 26 June 2018

ER -

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

Polynomial-Time Algorithms for Phylogenetic Inference Problems

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this