pith. sign in

arxiv: 1907.08474 · v1 · pith:QUEGF2MEnew · submitted 2019-07-19 · 💻 cs.DM · math.CO· q-bio.PE

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 This is my paper

Pith reviewed 2026-05-24 19:00 UTC · model grok-4.3

classification 💻 cs.DM math.COq-bio.PE
keywords tree-child networksphylogenetic networksfixed-parameter algorithmscherry picking sequencesreticulation minimizationbinary trees
0
0 comments X

The pith

The first fixed-parameter algorithm constructs minimum-reticulation tree-child networks displaying multiple binary trees using cherry-picking sequences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces an algorithm that builds a tree-child phylogenetic network from any number of binary trees, minimizing the number of reticulations. The method is fixed-parameter tractable with runtime depending on the reticulation number k. It employs cherry picking sequences to guide the search for the optimal network. The approach scales to 100 trees on ordinary computers, marking a practical advance for phylogenetic analysis.

Core claim

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((8k)^k poly(n, t)) time.

What carries the argument

Cherry picking sequences, which allow encoding and searching the structure of tree-child networks to find the one with minimum reticulations.

If this is right

  • The reticulation number of a set of trees can be computed exactly when it is small.
  • Tree-child networks can be constructed for instances with more input trees than previous exact methods allowed.
  • An efficient parallel implementation makes the algorithm usable on standard hardware.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If cherry picking sequences generalize to other network types, similar FPT algorithms might apply there.
  • Such networks could help reconcile conflicting phylogenetic signals in evolutionary biology data sets.
  • Testing on real biological data would show whether the minimum reticulation assumption holds in practice.

Load-bearing premise

The cherry-picking sequence framework correctly encodes the structure of tree-child networks and permits an exact search for the minimum reticulation number.

What would settle it

Finding a set of input trees where the algorithm produces a network with more reticulations than some known tree-child network that displays all the trees.

Figures

Figures reproduced from arXiv: 1907.08474 by Leo van Iersel, Mark Jones, Norbert Zeh, Remie Janssen, Yukihiro Murakami.

Figure 1
Figure 1. Figure 1: (a) A phylogenetic network that is not tree-child because both children of the red node are [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) An optimal tree-child network for the four trees in Figure 1b. Note that this network [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The construction of the tree Tˆ(j) from T (j) and a caterpillar C with leaf set {z, xi1 , . . . , xi` }. Proof. For j = 0, the claim holds by Lemma 10. For j > 0, we cannot apply Lemma 10 directly because the trees in T (j) may have different leaf sets. Assume that T (j) has no trivial cherry, because otherwise the lemma holds. In order to use Lemma 10 to bound the number of unique cherries in T (j) , we t… view at source ↗
Figure 4
Figure 4. Figure 4: The speed-up (running time without redundant branch elimination divided by the running time [PITH_FULL_IMAGE:figures/full_fig_p029_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Running times of our algorithm with and without redundant branch elimination, as functions [PITH_FULL_IMAGE:figures/full_fig_p029_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Running times of our algorithm on real-world data as a function of the reticulation number [PITH_FULL_IMAGE:figures/full_fig_p030_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The reticulation number and the level as a function of the number of leaves and trees in the [PITH_FULL_IMAGE:figures/full_fig_p030_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Running times of the algorithm with redundant branch elimination on al synthetic test inputs [PITH_FULL_IMAGE:figures/full_fig_p031_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Running times of our algorithm and HYBROSCALE on synthetic inputs. Since our algorithm solves all test instances and HYBROSCALE does not, we choose the tree-chlid hybridization number as the x-axis. Bars indicate a 95% confidence interval. Stars indicate significant differences between the running times of the two algorithms using an independent t-test with unequal variances (*: p < 0.05, **: p < 0.01). 6 … view at source ↗
Figure 10
Figure 10. Figure 10: Running times of our algorithm and HYBROSCALE on real-world inputs. Since our algorithm solves all test instances that HYBROSCALE was able to solve, we chose the tree-child level as the x-axis. Bars indicate a 95% confidence interval. Stars indicate significant differences between the running times of the two algorithms using an independent t-test with unequal variances (*: p < 0.05, **: p < 0.01). 34 [P… view at source ↗
read the original 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((8k)^k \mathrm{poly}(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper presents the first fixed-parameter algorithm for constructing a tree-child phylogenetic network displaying an arbitrary number of binary input trees with the minimum number of reticulations. It uses the cherry-picking sequence framework, runs in O((8k)^k poly(n,t)) time, and includes an efficient parallel implementation shown to handle up to 100 input trees on standard hardware.

Significance. If the correctness proofs and runtime analysis hold, this is a notable advance in computational phylogenetics: the first FPT result for minimum-reticulation tree-child networks from multiple trees, with explicit branching analysis and a practical parallel implementation that improves on prior methods. The manuscript supplies reduction rules, branching analysis, and correctness arguments for the cherry-picking approach.

minor comments (2)
  1. [§4] §4 (Algorithm description): the pseudocode for the branching step on cherry-picking sequences would benefit from an explicit small example showing how a single reduction rule is applied to a set of three trees.
  2. [Experimental evaluation] The experimental section reports runtimes but does not include a direct comparison table against the previous exponential-time methods cited in the introduction; adding one would strengthen the 'major improvement' claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its significance as the first FPT algorithm for this problem, and the recommendation for minor revision. No specific major comments appear in the provided referee report.

Circularity Check

0 steps flagged

No significant circularity; algorithmic construction is self-contained

full rationale

The paper presents an explicit FPT algorithm for minimum-reticulation tree-child networks, including reduction rules, branching analysis that produces the (8k)^k factor, and correctness proofs that shortest cherry-picking sequences yield the desired networks. These elements are derived directly from the input trees and the sequence framework without reducing any central claim to a fitted parameter, self-defined quantity, or unverified self-citation chain. The framework is used as an established encoding tool whose properties are leveraged with independent proofs supplied in the manuscript, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based on abstract only. No free parameters, invented entities, or non-standard axioms are identifiable from the given text.

axioms (1)
  • domain assumption The cherry picking sequence framework correctly models tree-child phylogenetic networks.
    The algorithm is built directly on this framework as stated in the abstract.

pith-pipeline@v0.9.0 · 5669 in / 1178 out tokens · 24132 ms · 2026-05-24T19:00:46.419934+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    Computing Hybridization Networks for Multiple Rooted Binary Phylogenetic Trees by Maximum Acyclic Agreement Forests

    Benjamin Albrecht. Computing hybridization networks for multiple rooted binary phylogenetic trees by maximum acyclic agreement forests. arXiv:1408.3044, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  2. [2]

    Computing all hybridization networks for multiple binary phylogenetic input trees

    Benjamin Albrecht. Computing all hybridization networks for multiple binary phylogenetic input trees. BMC Bioinformatics, 16(1):236, 2015

    work page 2015

  3. [3]

    Baroni, C

    M. Baroni, C. Semple, and M. Steel. Hybrids in real time. Systematic Biology, 55:46–56, 2006

    work page 2006

  4. [4]

    Bounding the number of hybridisation events for a consistent evolutionary history

    Mihaela Baroni, Stefan Grünewald, Vincent Moulton, and Charles Semple. Bounding the number of hybridisation events for a consistent evolutionary history. Journal of Mathematical Biology , 51(2):171–182, 2005

    work page 2005

  5. [5]

    Robert G. Beiko. Telling the whole story in a 10,000-genome world. Biology Direct, 6(1):34, 2011

    work page 2011

  6. [6]

    John, and Charles Semple

    Magnus Bordewich, Simone Linz, Katherine St. John, and Charles Semple. A reduction algorithm for computing the hybridization number of two trees. Evolutionary Bioinformatics Online, 3:86–98, 2007

    work page 2007

  7. [7]

    Computing the hybridization number of two phyloge- netic trees is fixed-parameter tractable

    Magnus Bordewich and Charles Semple. Computing the hybridization number of two phyloge- netic trees is fixed-parameter tractable. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(3):458–466, 2007

    work page 2007

  8. [8]

    Personal communication, June 2019

    Sander Borst. Personal communication, June 2019

    work page 2019

  9. [9]

    Algorithms for reticulate networks of multiple phylogenetic trees

    Zhi-Zhong Chen and Lusheng Wang. Algorithms for reticulate networks of multiple phylogenetic trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9(2):372–384, 2012

    work page 2012

  10. [10]

    Humphries, Simone Linz, and Charles Semple

    Peter J. Humphries, Simone Linz, and Charles Semple. Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies. Bulletin of Mathematical Biology , 75(10):1879–1890, 2013

    work page 2013

  11. [11]

    Hybridization number on three rooted binary trees is EPT

    Leo van Iersel, Steven Kelk, Nela Lekic, Chris Whidden, and Norbert Zeh. Hybridization number on three rooted binary trees is EPT. SIAM Journal on Discrete Mathematics, 30(3):1607–1631, 2016. 35

    work page 2016

  12. [12]

    Kernelizations for the hybridization number problem on multiple nonbinary trees

    Leo van Iersel, Steven Kelk, and Celine Scornavacca. Kernelizations for the hybridization number problem on multiple nonbinary trees. Journal of Computer and System Sciences, 82(6):1075–1089, 2016

    work page 2016

  13. [13]

    A quadratic kernel for computing the hybridization number of multiple trees

    Leo van Iersel and Simone Linz. A quadratic kernel for computing the hybridization number of multiple trees. Information Processing Letters, 113(9):318–323, 2013

    work page 2013

  14. [14]

    Treetistic

    Steven Kelk. Treetistic. http: //skelk.sdf-eu.org/clustistic/, 2012

    work page 2012

  15. [15]

    Computing maximum agreement forests without cluster partitioning is folly

    Zhijiang Li and Norbert Zeh. Computing maximum agreement forests without cluster partitioning is folly . InProceedings of the 25th Annual European Symposium on Algorithms, pages 56:1–56:14, 2017

    work page 2017

  16. [16]

    A cluster reduction for computing the subtree distance between phylogenies

    Simone Linz and Charles Semple. A cluster reduction for computing the subtree distance between phylogenies. Annals of Combinatorics, 15(3):465–484, 2011

    work page 2011

  17. [17]

    Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies

    Simone Linz and Charles Semple. Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies. Advances in Applied Mathematics, 105:102–129, 2019

    work page 2019

  18. [18]

    Fast construction of near parsimonious hybridization networks for multiple phylogenetic trees

    Sajad Mirzaei and Yufeng Wu. Fast construction of near parsimonious hybridization networks for multiple phylogenetic trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13(3):565–570, 2016

    work page 2016

  19. [19]

    Beiko, and Norbert Zeh

    Chris Whidden, Robert G. Beiko, and Norbert Zeh. Fixed-parameter algorithms for maximum agreement forests. SIAM Journal on Computing, 42(4):1431–1466, 2013

    work page 2013

  20. [20]

    Supertrees based on the subtree prune- and-regraft distance

    Christopher Whidden, Norbert Zeh, and Robert G Beiko. Supertrees based on the subtree prune- and-regraft distance. Systematic biology, 63(4):566–581, 2014

    work page 2014

  21. [21]

    Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees

    Yufeng Wu. Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees. Bioinformatics, 26(12):i140–i148, 2010. 36 A Construction of a Tree-Child Network from a Tree-Child Cherry Picking Sequence Procedure TREECHILD NETWORK FROMSEQUENCE (T, S) Input: A set of X-trees T and a tree-child cherry picking sequence S = 〈(x1, y...

    work page 2010