A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

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

doi:10.1007/s00453-021-00914-8

A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

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

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Contribution to journal › Article › Scientific › peer-review

5 Citations (Scopus)

19 Downloads (Pure)

Abstract

We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O((8 k) ^kpoly (n, t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.

Original language	English
Pages (from-to)	917-960
Number of pages	44
Journal	Algorithmica
Volume	84
Issue number	4
DOIs	https://doi.org/10.1007/s00453-021-00914-8
Publication status	Published - 2022

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

Fixed-parameter algorithms
Hybridization number
Phylogenetic networks

Access to Document

10.1007/s00453-021-00914-8

Iersel2022_Article_APracticalFixed-ParameterAlgorFinal published version, 6.72 MB

Cite this

@article{70e72477d6164b6fa275f16df603453b,

title = "A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees",

abstract = "We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O((8 k) kpoly (n, t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.",

keywords = "Fixed-parameter algorithms, Hybridization number, Phylogenetic networks",

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

year = "2022",

doi = "10.1007/s00453-021-00914-8",

language = "English",

volume = "84",

pages = "917--960",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

AU - van Iersel, Leo

AU - Janssen, Remie

AU - Jones, Mark

AU - Murakami, Yukihiro

AU - Zeh, Norbert

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

PY - 2022

Y1 - 2022

N2 - We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O((8 k) kpoly (n, t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.

AB - We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O((8 k) kpoly (n, t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.

KW - Fixed-parameter algorithms

KW - Hybridization number

KW - Phylogenetic networks

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

U2 - 10.1007/s00453-021-00914-8

DO - 10.1007/s00453-021-00914-8

M3 - Article

AN - SCOPUS:85124761100

SN - 0178-4617

VL - 84

SP - 917

EP - 960

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -

A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this