Counting doubly labelled trees and one-component networks
summary
The gist
A bijection between one-component networks on k taxa and rooted binary multi-labelled trees in which every label occurs exactly twice is established to derive a closed formula for counting…
In short
The paper establishes a bijection between one-component networks on k taxa and fully doubled DUP-trees where every label appears twice. This connection allows for a closed formula to count these networks, including explicit formulas for counting them with a specific number of reticulations. The method uses Burnside's lemma and detailed counting of DUP-trees.
Key concepts
- One-component networks
- These are phylogenetic networks on k taxa that have no reticulation vertices. Essentially, they represent evolutionary histories where lineages merge only through standard bifurcations (splits), without any instances of hybridization or reticulation.
- Fully doubled DUP-trees
- These are specific multi-labelled trees where every label assigned to a leaf node appears exactly twice across the entire tree structure. This structure is used as the combinatorial object corresponding to one-component networks.
- Bijection
- A mapping between two different types of mathematical objects—in this case, one-component networks and fully doubled DUP-trees. This correspondence is crucial because it allows researchers to use the known counting methods for trees to solve the counting problem for networks.
- Reticulations
- These are vertices in a phylogenetic network that represent events where two or more lineages merge, such as hybridization or incomplete lineage sorting. The paper provides formulas to count networks based on a prescribed number of these reticulation points.
Terminology used across episodes
This episode discusses
The paper
Counting doubly labelled trees and one-component networks · Read on arXiv
LOUXIN ZHANG
National University of Singapore
A phylogenetic network is one-component if the child of every reticulation is a leaf. This class of networks has been widely used as building blocks in the combinatorial study of phylogenetic networks. We establish a bijection between one-component networks on k taxa and rooted binary multi-labelled trees in which every label occurs exactly twice. Using this bijection and Burnside's lemma, we derive a closed formula and a two-term recurrence for the number of one-component networks. We further obtain explicit formulas for counting one-component networks with a prescribed number of reticulations.
Transcript
Introduction to the show: ident: Genomics Radio. Generated commentary on the latest computational biology and genomics papers.
Ines: I'm Ines.
Marcus: And I'm Marcus, here with Yuki.
Ines: We're looking at the paper: "Counting doubly labelled trees and one-component networks".
Marcus: Here's the gist of the paper. A bijection between one-component networks on k taxa and rooted binary multi-labelled trees in which every label occurs exactly twice is established to derive a closed formula for counting one-component networks.
Ines: Establishing the Bijection The authors establish a bijection between one-component networks on k taxa and fully doubled DUP-trees, in which every label occurs exactly twice.
Marcus: This correspondence is used to derive a closed formula for the number of one-component networks Ok of k leaves.
Ines: The proof involves mapping a network to a DUP-tree by replacing each reticulation with leaf children and each non-reticulation leaf with a cherry, resulting in a rooted binary DUP-tree D(N).
Title and authors: Ines: So this paper, "Counting doubly labelled trees and one-component networks," it sets up a direct link between these complex evolutionary networks and something simpler called rooted binary multi-labelled trees where every label appears exactly twice.
Marcus: That's the main idea. They use this bijection to get a closed formula for counting one-component networks, which we call Ok of k leaves. It’s a huge simplification over whatever recurrence relations we might be dealing with otherwise >
Yuki: For me, the focus on these one-component networks is interesting because they are used as building blocks in the combinatorial study of phylogenetic networks, and this paper seems to give us a concrete counting method for them >
Ines: Exactly. They establish this mapping by taking a network and turning each reticulation into leaf children and each non-reticulation leaf into something called a cherry, which results in a rooted binary DUP-tree D of N >
Marcus: And then they use Burnside's lemma with this bijection to derive that closed formula for Ok and also get this two term recurrence relation >
Yuki: That recurrence relation itself seems interesting because it relates the number of those DUP-trees with specific label counts, which is how we count them in a tree structure >
Ines: Right. The paper then goes on to detail how to count these DUP-trees themselves by looking at the number of singleton labels and the number of labels that occur twice, ms,i >
Marcus: They give us an explicit counting formula for those DUP-trees using sums over m, where m relates to how many twin cherries you have >
Yuki: And they state that this counting relies on this identity derived from contracting twin cherries in DUP-trees, which is a really elegant way to simplify the structure >
Ines: The real payoff for us is the explicit formula for Ok of k leaves with a prescribed number of reticulations, Ok i >
Marcus: That formula involves a double sum using terms P k minus i plus l and Q k minus i plus l, which is quite specific and allows us to calculate counts for networks with exactly i reticulations >
Yuki: And they also give examples like for ts one equals s times two s minus one double factorial, and ts two equals s plus one times two by two s plus three times two s minus one double factorial >
Ines: It’s a lot of notation, but the point is we have a direct way to count networks with a specific number of reticulations without relying on those high-order recurrence relations I mentioned earlier >
Marcus: And they also give us the total number Ok using another sum over j, which means we can get the overall count if we don't care about the exact number of reticulations >
Yuki: The paper also touches on the asymptotic behavior as k gets very large, showing that Ok scales like e to the power one over four root two pi times eight to the power k divided by n factorial squared >
Ines: That scaling result is interesting because it connects back to some known results in the literature and gives us a simple way to approximate these counts for very large numbers of taxa >
Marcus: What they also point out is that this counting method, which relies on the twin-cherry-free condition, actually complicates the recurrence relation that was found in a previous paper >
Yuki: So, while this paper gives us explicit formulas, it highlights where those simpler recurrences might fail when you consider more complex constraints like avoiding twin cherries >
Ines: Right. It seems like the main contribution here is providing these explicit counting tools for networks with a fixed number of reticulations and showing how to count the underlying tree structures efficiently >
Marcus: So, to wrap up, we have this paper, "Counting doubly labelled trees and one-component networks," which establishes a bijection to fully doubled DUP-trees and provides explicit formulas for counting one-component networks with a specific number of reticulations i >
Yuki: It gives us concrete numbers for these structures on k taxa up to seven, which is really helpful for testing hypotheses about network complexity >
Ines: And they show the way to count them when there are exactly i reticulations, giving us Ok i using that double sum structure >
Marcus: We should keep an eye on how this counting method applies when we look at galled networks, since the paper suggests that the twin-cherry-free condition makes things tricky for those other network types >
The paper's summary: Ines: So, this paper boils down to finding a way to count these complex evolutionary networks by relating them directly to something simpler: rooted binary multi-labelled trees where every single label appears exactly twice.
Marcus: That's right, Ines, and the core of it is using that mapping—that bijection—to build a closed formula for counting what they call one-component networks, which we just call Ok of k leaves.
Yuki: From a population genetics view, this means they’ve given us a concrete mathematical tool to estimate how many different network topologies are possible when you have k taxa, which is something we usually can only guess at with simulations.
Ines: Exactly. They take the structure of a network, and they replace every single branching point that isn't a reticulation with what’s called a cherry, and every reticulation becomes leaf children, which turns it into this fully doubled DUP-tree.
Marcus: And they use Burnside's lemma on that tree counting problem to get that final closed formula for Ok and also a recurrence relation for it. That recurrence relation is what lets them count the underlying tree structures efficiently too.
Yuki: It’s interesting because these trees with repeated labels, the DUP-trees, are fundamentally structured in a way that mimics how genetic relationships evolve over time across a lineage.
Ines: Right. And they spend a lot of time detailing how to count those DUP-trees themselves based on how many times labels appear once versus twice. They have this formula that looks like it involves sums over m, which tracks the twin cherries, and that’s their way of handling the complexity of the tree structure.
Marcus: The explicit counting for Ok,i—the number of networks with exactly i reticulations—is given by a double sum involving terms P k minus i plus l and Q k minus i plus l. That formula is quite specific, and it lets you calculate counts for networks with a fixed number of reticulations without needing those high-order recurrence formulas they mentioned before.
Yuki: It’s like they’re giving us the exact recipe to bake these networks with a precise number of reticulation events, which should help us test our models against real biological data more rigorously.
Ines: And they also provide some concrete examples of these terms, like for ts one being s times two s minus one double factorial, which gives you a specific starting point for the calculation. That’s how you get the raw numbers to start building intuition about the complexity.
Marcus: So, what this paper really does is move us away from just having vague recurrence relations and gives us a direct formula based on leaf count and reticulation count. It makes calculating these network counts much more feasible computationally, which is crucial for large cohort studies.
Yuki: It supports the idea that there’s a deep combinatorial structure underpinning these evolutionary processes, which is important for understanding how species actually diversify and branch out.
Ines: And they also look at how this all scales as the number of leaves k gets really big, showing an asymptotic behavior that connects back to some known results in the literature. That gives us a sense of the overall complexity when we have thousands of taxa to consider.
Marcus: It’s a solid piece for computational biology because it provides explicit counting tools, and they also flag that this method relies on avoiding twin cherries, which shows where these simpler models might break down when you look at more realistic network structures.
Yuki: So, while they give us powerful counting methods for one-component networks with a fixed number of reticulations, the paper leaves the door open to see how this approach handles the more complicated galled networks we discussed earlier.
The paper's improvements: Tom: So, we're moving on to how they suggest making this counting method better for future work and other related problems.
Ines: They point out that while this method works well for one-component networks with a fixed number of reticulations, it doesn't directly address the more complex galled networks.
Marcus: That’s because the twin cherry condition they rely on is too restrictive for those other network types we talked about previously.
Yuki: And they suggest that finding an equally simple counting formula for galled networks might be really hard, which is a big warning sign for us as population geneticists looking at real-world data.
Ines: They also note that the explicit formulas they derived, like the double sum with P and Q terms, are very specific to this bijection with fully doubled DUP-trees.
Marcus: So, the improvement they suggest is more of an extension—they want to see if we can find a similar bijection for those galled networks, which would unlock a simpler counting formula for them too.
Yuki: If they could do that, it would give us a powerful way to compare theoretical predictions with empirical observations of species evolution across different network types.
Ines: It’s about extending the combinatorial machinery. They’re hoping that by understanding the structure of these DUP-trees so well, we can apply those insights to other related phylogenetic structures.
Marcus: From a data science standpoint, if we could get a simple formula for galled networks, it would mean we could perform exact counting on larger cohorts where approximations are getting messy due to batch effects or missing data.
Yuki: It changes how much statistical power we have when testing hypotheses about the evolutionary history of a species because it gives us a better way to count the possibilities.
Ines: So, for now, it’s less about fixing this paper and more about using its successful counting framework as a template to try and solve the problem for those other network types.
Marcus: Exactly. The implication is that this bijection itself is a key structural concept, not just a tool for one specific type of network.
Conclusion: Tom: So we're wrapping up this session by summarizing what they actually achieved with the paper "Counting doubly labelled trees and one-component networks."
Ines: The main thing is that they built a way to count those complex one-component networks using a bijection to fully doubled DUP-trees, giving us closed formulas for counting them based on the number of leaves and reticulations.
Marcus: That means we can get explicit numbers for how many different network structures are possible for a given number of taxa, which is huge for large cohort studies where we need exact statistics.
Yuki: From a population geneticist's view, it’s about having a concrete way to compare theoretical possibilities against the actual diversity we see in species across different evolutionary paths.
Ines: Right. They also provided an asymptotic result showing how these network counts scale as the number of taxa gets really large, which helps us understand the overall complexity at scale.
Marcus: And they showed that this counting method is more robust than some previous recurrence relations because it handles those fixed numbers of reticulations much better.
Yuki: It confirms that there's a deep combinatorial structure here, which tells us something about how biological diversity itself is constrained by these mathematical rules.
Ines: The paper shows the way to count these networks with a specific number of reticulations using that double sum structure involving terms P and Q, which is really helpful for calculating Ok i.
Marcus: It’s practical because it gives us a formula we can actually plug numbers into to get an answer, instead of just relying on a recurrence relation that gets very complicated fast.
Yuki: So, the implication is that we have a more precise tool to model network evolution in real biological systems.
Ines: Yeah. The limitation they point out is that this specific counting method relies on avoiding twin cherries, so it doesn't directly apply to galled networks without some serious work.
Marcus: So, the paper gives us a very specific toolkit for one-component networks, but we still have the challenge of extending this counting logic to those more complicated structures.
Yuki: That leads us right into what we talked about before—trying to find an equally simple way to count galled networks so we can fully map out the landscape of possible evolutionary trees.
More episodes
- 2610.33881-Sensorimotor behavior from an untrained brain-and-nerve-cord connectome
- 2610.40344-Morphological Features of Murine Pulmonary Arterial Networks for Diagnosing Vascular Disease
- Daily Summary for 2026-11-19
- 2609.10193-Are You Learning Biological Signal or Shortcuts? Auditing and Mitigating Bias in Protein-Protein Interaction Datasets
- 2610.38236-Generative discovery of chemical reaction networks
- 2507.11176-An Interpretable AI framework Quantifying Traditional Chinese Medicine Principles Towards Enhancing and Integrating with Modern Biomedicine
- The day in conversation for 2026-11-19
- Daily Summary for 2026-11-19
- 2504.03590-Towards a Unified Framework for Determining Conformational Ensembles of Disordered Proteins
- 2603.15217-A multiscale discrete-to-continuum framework for structured population models