arxiv: 2605.06243 · v1 · submitted 2026-05-07 · 🧮 math.CO · q-bio.PE

Recognition: unknown

A μ-distance for semidirected orchard phylogenetic networks

Gerard Ribas , Joan Carles Pons , C\'ecile An\'e

Authors on Pith no claims yet

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

classification 🧮 math.CO q-bio.PE

keywords phylogenetic networkssemidirected networksorchard networksμ-representationnetwork distancereconstruction algorithmevolutionary biologycombinatorics

0 comments

The pith

A new edge-based μ-representation distinguishes binary orchard semidirected networks and supports a polynomial-time distance.

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

The paper introduces an edge-based variant of the μ-representation for semidirected phylogenetic networks restricted to the orchard class. This representation records structural features such as paths to reticulation points and edge counts to produce a signature for each network. A reconstruction algorithm recovers the original network from the signature, which directly defines a distance that meets all metric properties and runs in polynomial time. Biologists comparing possible evolutionary histories that include reticulation events can therefore measure differences between networks without first resolving edge directions or root positions.

Core claim

The central claim is that a suitably defined edge-based μ-representation is injective on binary orchard semidirected networks. An accompanying reconstruction algorithm recovers any such network from its representation in polynomial time, and the resulting function between pairs of networks satisfies the axioms of a distance.

What carries the argument

The edge-based μ-representation, which assembles counts of paths from leaves to reticulations together with other edge statistics to serve as a unique identifier for each network.

If this is right

Distances between distinct evolutionary histories modeled by these networks can be computed efficiently.
The network itself can be rebuilt from the representation alone.
The resulting function satisfies symmetry, non-negativity, and the triangle inequality.
Comparisons of semidirected networks inferred from genetic data become practical for this restricted class.

Where Pith is reading between the lines

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

The same representation idea might be adapted to other restricted families of semidirected networks if injectivity can be shown.
Software for phylogenetic analysis could incorporate this distance for rapid pairwise comparisons.
The reconstruction procedure suggests a route toward canonical labeling or canonical forms for these networks.

Load-bearing premise

Distinct binary orchard semidirected networks must always produce distinct edge-based μ-representations.

What would settle it

Any pair of non-isomorphic binary orchard semidirected networks that share the same edge-based μ-representation would disprove injectivity and collapse the claimed distance.

Figures

Figures reproduced from arXiv: 2605.06243 by C\'ecile An\'e, Gerard Ribas, Joan Carles Pons.

**Figure 1.** Figure 1: Top: example of a semidirected [5]-network N. It has two root components T1 and T2, unresolved and highlighted in red. T1 is trivial whereas T2 is not. e8 is the unique undirected edge. Bottom: µ-representation µ(N). Brackets and parentheses have been removed for readability. becomes a directed cycle. A semidirected graph is said to be acyclic if it does not contain any semidirected cycle. We refer to dire… view at source ↗

**Figure 2.** Figure 2: Binary [2]-network N2, to illustrate counting paths m(u, 1; e) that avoid an edge e. For example, m(u, 1; he) = 1 from the path through hi, and m(u, 1) = 2 in total. We will see in section II that (1, 2) is a reticulate cherry and that N2 is an orchard network. The µ-entry for edge he, defined later in section III, is {((1, 1, 0), :h), ((1, 1, 1), :i)}. [u] is the subgraph of N induced by the nodes of N in… view at source ↗

**Figure 3.** Figure 3: Left: Reduction (→) and addition (←) of cherry (a, b) of each type. In reticulate cherries, the hybrid internal (hi) and external (he) edges are shown in blue. Right: µ-entries, as defined later in section III, before and after cherry reduction, where m and me are µ-vectors that depend on the rest of the network. ¿m:i? means that the tagged µ-vector may be absent, and brackets and parentheses are omitted f… view at source ↗

**Figure 4.** Figure 4: Top: Reduction of N by the complete reduction sequence S = (4, 5)(3, 2)(1, 2)(3, 5)(4, 5). Bottom: µ1 = µ (4,5) 0 , . . . , µ5 = µ (4,5) 4 constructed by the cherry reduction loop in Algorithm 1 from µ0 = µ(N). The tags that are modified with respect to the previous µ-representation are highlighted in blue. The addition loop then constructs Nk such that µk = µ(Nk). Each cherry is indicated with its type ne… view at source ↗

**Figure 5.** Figure 5: Top: [7]-network N reduced to the trivial forest on {1, 2, 4} by the cherry-reduction sequence (1, 2)(3, 4)(5, 1)(1, 4)(3, 5)(5, 2)(5, 6)(6, 7)(7, 1). The network N′ obtained from N by swapping taxon labels 2 and 4 is not isomorphic to N. With our µ-representation that includes :i tags, µ(N) ̸= µ(N′ ) although are similar: they have the same multiset of tagged µ-vectors when the components with the :i tag … view at source ↗

**Figure 6.** Figure 6: [6]-network N without any cherry, hence not orchard. The network N′ obtained by swapping taxa 5 and 6 is not isomorphic to N. Yet N and N′ have the same edge-based µ-representation. In fact, each µ-entry is invariant to swapping 5 and 6. For example, the root component (red edges) has simple µ-vector (8, 2, 2, 2, 2, 1, 1), and µ(e) = {((4, 1, 1, 1, 1, 1, 0), :t), ((4, 1, 1, 1, 1, 0, 1), :t)}. CODE AVAILA… view at source ↗

read the original abstract

In evolutionary biology, phylogenetic networks are now widely used to represent the historical relationships between species and population, when this history includes reticulation events such as hybridization, gene flow and admixture between populations. Semidirected phylogenetic networks are appropriate models when the direction of some edges and the root position are not identifiable from data. Comparing semidirected networks is important in many applications. For rooted and directed networks, a $\mu$-representation was originally introduced to distinguish tree-child networks, and has since been extended in two different directions: to the larger class of orchard directed networks by adding an extra component that counts paths to reticulations; and to semidirected networks, through an edge-based variant. However, the latter does not provide a distance between semidirected and orchard networks. We introduce here a new edge-based $\mu$-representation capable of distinguishing distinct orchard binary semidirected networks. For this class, we provide a reconstruction algorithm and therefore obtain a true distance that is computable in polynomial time.

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.

Desk Editor's Note private letter to a colleague

The paper defines a new edge-based μ-representation that injects on binary orchard semidirected networks and supplies a polynomial-time reconstruction algorithm to turn it into a distance.

read the letter

This paper introduces an edge-based μ-representation that distinguishes distinct binary orchard semidirected phylogenetic networks and includes a reconstruction algorithm running in polynomial time, which gives a computable distance. It extends the μ-representation idea from rooted directed networks to the semidirected case for the orchard subclass. The edge-based variant avoids the need for additional components that count paths to reticulations, which was necessary in some directed extensions. Instead, it uses the edges directly to create a representation that is unique for each network in this class. What stands out is the provision of the reconstruction algorithm. This not only proves the representation is injective but also makes the distance practical to compute, which is important for biological applications where you might have many networks to compare. The main soft spot is how narrow the class is. Binary orchard semidirected networks are a specific type, and while the paper focuses there, it leaves open whether similar ideas could work more broadly. Also, the uniqueness relies on the algorithm being correct, so the proof of that algorithm's correctness is central. This work is for combinatorialists and biologists working with phylogenetic networks, particularly when dealing with semidirected models from data with unidentifiable roots or directions. Someone looking for a new metric in this area would get something concrete. I think it deserves peer review. The contribution is clear and the claims are scoped appropriately, so referees can check the algorithm details.

Referee Report

1 major / 2 minor

Summary. The manuscript introduces a new edge-based μ-representation for binary orchard semidirected phylogenetic networks. It asserts that this representation is injective on the class (distinct networks yield distinct representations), supplies an explicit reconstruction algorithm from the representation back to the network, and concludes that the induced distance is computable in polynomial time.

Significance. If the injectivity and reconstruction claims hold, the work supplies a practical, polynomial-time distance for comparing semidirected networks that model reticulation events. This extends earlier μ-representations (originally for tree-child directed networks and later for orchard directed networks) to the semidirected setting while preserving computational tractability, which is valuable for phylogenetic applications where root and edge directions are not identifiable from data.

major comments (1)

[Proof of Theorem on reconstruction (likely §4 or §5)] The central claim of injectivity and the correctness of the reconstruction algorithm rest on the proofs supplied in the manuscript. Because the abstract and high-level description do not contain the full argument, the load-bearing step (that the edge-based μ-representation uniquely determines the network within the binary orchard semidirected class) cannot be verified from the provided summary alone; explicit verification of the proof of uniqueness and of the polynomial-time bound is required before acceptance.

minor comments (2)

[Abstract] The abstract states that the new representation 'does not provide a distance between semidirected and orchard networks' for the prior variant; a brief sentence clarifying why the new edge-based version succeeds where the earlier one did not would improve readability.
[Section 2 or 3 (definition)] Notation for the edge-based μ-representation (e.g., how the extra path-counting component is incorporated) should be introduced with a small illustrative example early in the text to aid readers unfamiliar with the directed-network precursors.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of the potential impact of our work on semidirected phylogenetic networks. We respond point by point to the major comment below.

read point-by-point responses

Referee: [Proof of Theorem on reconstruction (likely §4 or §5)] The central claim of injectivity and the correctness of the reconstruction algorithm rest on the proofs supplied in the manuscript. Because the abstract and high-level description do not contain the full argument, the load-bearing step (that the edge-based μ-representation uniquely determines the network within the binary orchard semidirected class) cannot be verified from the provided summary alone; explicit verification of the proof of uniqueness and of the polynomial-time bound is required before acceptance.

Authors: The manuscript contains the complete proofs. Injectivity of the edge-based μ-representation on binary orchard semidirected networks is established in Theorem 4.1 (Section 4), which proceeds by showing that the representation determines the set of leaves, the reticulation edges, and the underlying tree structure via a unique decomposition that exploits the orchard property (every reticulation has a unique path from a leaf). The reconstruction algorithm is presented as Algorithm 1 in Section 4.2; its correctness is proven by induction on the number of reticulations, verifying at each step that the μ-values allow unambiguous identification of the next leaf or reticulation to resolve. The polynomial-time bound is derived in Theorem 5.1 (Section 5), where we show that each of the O(n) reconstruction steps can be implemented in O(n²) time using standard graph traversal on the representation, for an overall O(n³) complexity. These arguments are self-contained within the manuscript and do not rely on external results beyond standard facts about phylogenetic networks. If the referee finds any particular lemma or step insufficiently detailed, we are prepared to expand the exposition in a revised version. revision: no

Circularity Check

0 steps flagged

No significant circularity; new representation is a direct combinatorial definition

full rationale

The paper defines a new edge-based μ-representation directly and proves injectivity on binary orchard semidirected networks via an explicit reconstruction algorithm. This construction is self-contained and does not reduce any claimed distance or prediction to a fitted parameter, self-citation chain, or input by definition. Prior μ-representations are cited only for context and are not load-bearing for the new result or its polynomial-time computability.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claim rests on standard definitions from graph theory for directed and semidirected networks together with the new combinatorial definition of the edge-based μ-vector; no free parameters or invented entities beyond the representation itself are introduced.

axioms (1)

standard math Standard definitions of phylogenetic networks, orchard networks, and semidirected networks from prior literature.
The paper builds directly on established combinatorial notions of networks and reticulations.

invented entities (1)

edge-based μ-representation no independent evidence
purpose: To encode and distinguish binary semidirected orchard networks
Newly defined combinatorial object whose uniqueness is asserted for the target class.

pith-pipeline@v0.9.0 · 5477 in / 1207 out tokens · 52388 ms · 2026-05-08T08:19:06.871151+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references · 22 canonical work pages

[1]

Modeling hybridization under the network multispecies coalescent,

J. H. Degnan, “Modeling hybridization under the network multispecies coalescent,”Systematic Biology, vol. 67, no. 5, pp. 786–799, 2018.DOI: 10.1093/sysbio/ syy040

work page doi:10.1093/sysbio/ 2018
[2]

Phylogenomic ap- proaches to detecting and characterizing introgression,

M. S. Hibbins and M. W. Hahn, “Phylogenomic ap- proaches to detecting and characterizing introgression,” Genetics, vol. 220, no. 2, iyab173, 2022.DOI: 10.1093/ genetics/iyab173

2022
[3]

Phylogenetic networks empower biodiversity research,

S. Kong, C. Sol ´ıs-Lemus, and G. P. Tiley, “Phylogenetic networks empower biodiversity research,”Proceedings of the National Academy of Sciences, vol. 122, no. 31, e2410934122, 2025.DOI: 10.1073/pnas.2410934122

work page doi:10.1073/pnas.2410934122 2025
[4]

Identifiability of local and global features of phylogenetic networks from average dis- tances,

J. Xu and C. An ´e, “Identifiability of local and global features of phylogenetic networks from average dis- tances,”Journal of Mathematical Biology, vol. 86, no. 1, p. 12, 2023.DOI: 10.1007/s00285-022-01847-8

work page doi:10.1007/s00285-022-01847-8 2023
[5]

Beyond level-1: Identifiability of a class of galled tree-child networks,

E. S. Allman, C. An ´e, H. Ba ˜nos, and J. A. Rhodes, “Beyond level-1: Identifiability of a class of galled tree-child networks,”Bulletin of Mathematical Biology, vol. 87, no. 166, 2025.DOI: 10 . 1007 / s11538 - 025 - 01545-8

2025
[6]

Identifiability of phyloge- netic level-2 networks under the Jukes-Cantor model,

A. K. Englander et al., “Identifiability of phyloge- netic level-2 networks under the Jukes-Cantor model,” bioRxiv, 2025.DOI: 10.1101/2025.04.18.649493

work page doi:10.1101/2025.04.18.649493 2025
[7]

Identifying circular orders for blobs in phylogenetic networks,

J. A. Rhodes, H. Ba ˜nos, J. Xu, and C. An ´e, “Identifying circular orders for blobs in phylogenetic networks,” Advances in Applied Mathematics, vol. 163, p. 102 804, 2025.DOI: 10.1016/j.aam.2024.102804

work page doi:10.1016/j.aam.2024.102804 2025
[8]

Evolutionary novelty in a butterfly wing pattern through enhancer shuffling,

R. W. R. Wallbank et al., “Evolutionary novelty in a butterfly wing pattern through enhancer shuffling,” PLOS Biology, vol. 14, no. 1, pp. 1–16, 2016.DOI: 10.1371/journal.pbio.1002353

work page doi:10.1371/journal.pbio.1002353 2016
[9]

General theory for stochastic admixture graphs and f-statistics,

S. Soraggi and C. Wiuf, “General theory for stochastic admixture graphs and f-statistics,”Theoretical Popula- tion Biology, vol. 125, pp. 56–66, 2019.DOI: 10.1016/ j.tpb.2018.12.002

2019
[10]

Forest- based networks,

K. T. Huber, V . Moulton, and G. E. Scholz, “Forest- based networks,”Bulletin of Mathematical Biology, vol. 84, p. 119, 2022.DOI: 10.1007/s11538-022-01081- 9 13

work page doi:10.1007/s11538-022-01081- 2022
[11]

A dissimilarity measure for semidirected networks,

M. Maxfield, J. Xu, and C. An ´e, “A dissimilarity measure for semidirected networks,”IEEE Transactions on Computational Biology and Bioinformatics, vol. 22, no. 02, pp. 684–696, 2025.DOI: 10 . 1109 / TCBBIO . 2025.3534780

work page arXiv 2025
[12]

Using max cut to enhance rooted trees consistency.IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):323–333, 2006

G. Cardona, F. Rossello, and G. Valiente, “Comparison of tree-child phylogenetic networks,”IEEE/ACM Trans- actions on Computational Biology and Bioinformatics, vol. 6, no. 4, pp. 552–569, 2009.DOI: 10.1109/TCBB. 2007.70270

work page doi:10.1109/tcbb 2009
[13]

On Nakhleh’s metric for reduced phylogenetic net- works,

G. Cardona, M. Llabres, F. Rossello, and G. Valiente, “On Nakhleh’s metric for reduced phylogenetic net- works,”IEEE/ACM Transactions on Computational Bi- ology and Bioinformatics, vol. 6, no. 4, pp. 629–638, 2009.DOI: 10.1109/TCBB.2009.33

work page doi:10.1109/tcbb.2009.33 2009
[14]

D. H. Huson, R. Rupp, and C. Scornavacca,Phyloge- netic Networks: Concepts, Algorithms and Applications. Cambridge: Cambridge University Press, 2010.DOI: 10. 1017/CBO9780511974076

2010
[15]

A metric on the space of reduced phy- logenetic networks,

L. Nakhleh, “A metric on the space of reduced phy- logenetic networks,”IEEE/ACM Transactions on Com- putational Biology and Bioinformatics, vol. 7, no. 2, pp. 218–222, 2010.DOI: 10.1109/TCBB.2009.2

work page doi:10.1109/tcbb.2009.2 2010
[16]

Defining phylogenetic network distances using cherry operations,

K. Landry, A. Teodocio, M. Lafond, and O. Tremblay- Savard, “Defining phylogenetic network distances using cherry operations,”IEEE/ACM Transactions on Com- putational Biology and Bioinformatics, vol. 20, no. 3, pp. 1654–1666, 2023.DOI: 10 . 1109 / TCBB . 2022 . 3162991

2023
[17]

Finding maximum common contractions between phylogenetic networks,

B. Marchand, N. Tahiri, S. G. Fard, O. Tremblay- Savard, and M. Lafond, “Finding maximum common contractions between phylogenetic networks,”Algo- rithms for Molecular Biology, vol. 20, p. 18, 2025.DOI: 10.1186/s13015-025-00283-9

work page doi:10.1186/s13015-025-00283-9 2025
[18]

On cherry-picking and network containment,

R. Janssen and Y . Murakami, “On cherry-picking and network containment,”Theoretical Computer Science, vol. 856, pp. 121–150, 2021.DOI: 10.1016/j.tcs.2020. 12.031

work page doi:10.1016/j.tcs.2020 2021
[19]

The comparison of tree-sibling time consistent phylo- genetic networks is graph isomorphism-complete,

G. Cardona, M. Llabr ´es, F. Rossell ´o, and G. Valiente, “The comparison of tree-sibling time consistent phylo- genetic networks is graph isomorphism-complete,”The Scientific World Journal, vol. 2014, p. 254 279, 2014. DOI: 10.1155/2014/254279

work page doi:10.1155/2014/254279 2014
[20]

Exploring spaces of semi- directed level-1 networks,

S. Linz and K. Wicke, “Exploring spaces of semi- directed level-1 networks,”Journal of Mathematical Biology, vol. 87, no. 70, 2023.DOI: 10.1007/s00285- 023-02004-5

work page doi:10.1007/s00285- 2023
[21]

Comparison of orchard networks using their extendedµ-representation,

G. Cardona, J. C. Pons, G. Ribas, and T. Mart ´ınez Coronado, “Comparison of orchard networks using their extendedµ-representation,”IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 21, no. 3, pp. 501–507, 2024.DOI: 10.1109/TCBB.2024. 3361390

work page doi:10.1109/tcbb.2024 2024
[22]

A class of phylogenetic networks reconstructable from ancestral profiles,

P. L. Erd ˝os, C. Semple, and M. Steel, “A class of phylogenetic networks reconstructable from ancestral profiles,”Mathematical Biosciences, vol. 313, pp. 33– 40, 2019,ISSN: 0025-5564.DOI: 10.1016/j.mbs.2019. 04.009

work page doi:10.1016/j.mbs.2019 2019
[23]

Defining phylogenetic networks using ancestral profiles,

A. Bai, P. L. Erd ˝os, C. Semple, and M. Steel, “Defining phylogenetic networks using ancestral profiles,”Math- ematical Biosciences, vol. 332, p. 108 537, 2021.DOI: 10.1016/j.mbs.2021.108537

work page doi:10.1016/j.mbs.2021.108537 2021
[24]

Orchard networks are trees with additional horizontal arcs,

L. van Iersel, R. Janssen, M. Jones, and Y . Murakami, “Orchard networks are trees with additional horizontal arcs,”Bulletin of Mathematical Biology, vol. 84, p. 76, 2022.DOI: 10.1007/s11538-022-01037-z

work page doi:10.1007/s11538-022-01037-z 2022
[25]

Metrics for classes of semi-binary phylogenetic networks using µ-representations,

C. Reichling, L. van Iersel, and Y . Murakami, “Metrics for classes of semi-binary phylogenetic networks using µ-representations,”Advances in Applied Mathematics, vol. 172, p. 102 953, 2026.DOI: 10.1016/j.aam.2025. 102953

work page doi:10.1016/j.aam.2025 2026
[26]

Characterizing semi-directed phylogenetic networks and their multi-rootable variants,

N. Holtgrefe, K. T. Huber, L. van Iersel, M. Jones, and V . Moulton, “Characterizing semi-directed phylogenetic networks and their multi-rootable variants,”Theory in Biosciences, vol. 145, p. 4, 2026.DOI: 10.1007/s12064- 025-00453-8

work page doi:10.1007/s12064- 2026
[27]

PhyloNet- works: A package for phylogenetic networks,

C. Sol ´ıs-Lemus, P. Bastide, and C. An ´e, “PhyloNet- works: A package for phylogenetic networks,”Molec- ular Biology and Evolution, vol. 34, no. 12, pp. 3292– 3298, 2017.DOI: 10.1093/molbev/msx235 SUPPLEMENTARYMATERIAL PROOF OF PROPOSITION5 To prove Proposition 5, we adapt the proof of Janssen and Murakami [18, Prop. 1], the analogous result for rooted ...

work page doi:10.1093/molbev/msx235 2017