Search

In recent years, there has been an effort to extend the classical notion of phylogenetic balance, originally defined in the context of trees, to networks. One of the most natural ways to do this is with the so-called $B_2$ index. In this paper, we study the $B_2$ index for a prominent class of phylogenetic networks: galled trees. We show that the $B_2$ index of a uniform leaf-labeled galled tree converges in distribution as the network becomes large. We characterize the corresponding limiting distribution, and show that its expected value is 2.707911858984... This is the first time that a balance index has been studied to this level of detail for a random phylogenetic network. One specificity of this work is that we use two different and independent approaches, each with its advantages: analytic combinatorics, and local limits. The analytic combinatorics approach is more direct, as it relies on standard tools; but it involves slightly more complex calculations. Because it has not previously been used to study such questions, the local limit approach requires developing an extensive framework beforehand; however, this framework is interesting in itself and can be used to tackle other similar problems.

The Sackin index is an important measure for the balance of phylogenetic trees. We investigate two extensions of the Sackin index to the class of galled trees and two of its subclasses (simplex galled trees and normal galled trees) where we consider both labeled and unlabeled galled trees. In all cases, we show that the mean of the Sackin index for a network which is uniformly sampled from its class is asymptotic to $\mu n^{3/2}$ for an explicit constant $\mu$. In addition, we show that the scaled Sackin index convergences weakly and with all its moments to the Airy distribution., Comment: Dedicated to Michael Drmota on the occasion of his 60th birthday. 25 pages

This paper addresses the significant challenge of recognizing behaviors in non-human primates, specifically focusing on chimpanzees. Automated behavior recognition is crucial for both conservation efforts and the advancement of behavioral research. However, it is significantly hindered by the labor-intensive process of manual video annotation. Despite the availability of large-scale animal behavior datasets, the effective application of machine learning models across varied environmental settings poses a critical challenge, primarily due to the variability in data collection contexts and the specificity of annotations. In this paper, we introduce ChimpBehave, a novel dataset featuring over 2 hours of video (approximately 193,000 video frames) of zoo-housed chimpanzees, meticulously annotated with bounding boxes and behavior labels for action recognition. ChimpBehave uniquely aligns its behavior classes with existing datasets, allowing for the study of domain adaptation and cross-dataset generalization methods between different visual settings. Furthermore, we benchmark our dataset using a state-of-the-art CNN-based action recognition model, providing the first baseline results for both within and cross-dataset settings. The dataset, models, and code can be accessed at: https://github.com/MitchFuchs/ChimpBehave, Comment: CV4Animals: Computer Vision for Animal Behavior Tracking and Modeling In conjunction with Computer Vision and Pattern Recognition 2024

We propose the class of galled tree-child networks which is obtained as intersection of the classes of galled networks and tree-child networks. For the latter two classes, (asymptotic) counting results and stochastic results have been proved with very different methods. We show that a counting result for the class of galled tree-child networks follows with similar tools as used for galled networks, however, the result has a similar pattern as the one for tree-child networks. In addition, we also consider the (suitably scaled) numbers of reticulation nodes of random galled tree-child networks and show that they are asymptotically normal distributed. This is in contrast to the limit laws of the corresponding quantities for galled networks and tree-child networks which have been both shown to be discrete., Comment: Submitted to AofA2024

We give exact and asymptotic counting results for the number of galled networks and reticulation-visible networks with few reticulation vertices. Our results are obtained with the component graph method, which was introduced by L. Zhang and his coauthors, and generating function techniques. For galled networks, we in addition use analytic combinatorics. Moreover, in an appendix, we consider maximally reticulated reticulation-visible networks and derive their number, too., Comment: Revised version; accepted for publication in Bull. Math. Biol

Given a gene-tree labeled topology $G$ and a species tree $S$, the "ancestral configurations" at an internal node $k$ of $S$ represent the combinatorially different sets of gene lineages that can be present at $k$ when all possible realizations of $G$ in $S$ are considered. Ancestral configurations have been introduced as a data structure for evaluating the conditional probability of a gene-tree labeled topology given a species tree, and their enumeration assists in describing the complexity of this computation. In the case that the gene-tree labeled topology $G=t$ matches that of the species tree $S$, by techniques of analytic combinatorics, we study distributional properties of the "total" number of ancestral configurations measured across the different nodes of a random labeled topology $t$ selected under the uniform and the Yule probability models. Under both of these probabilistic scenarios, we show that the total number $T_n$ of ancestral configurations of a random labeled topology of $n$ taxa asymptotically follows a lognormal distribution. Over uniformly distributed labeled topologies, the asymptotic growth of the mean and the variance of $T_n$ are found to satisfy $\mathbb{E}_{\rm U}[T_n] \sim 2.449 \cdot 1.333^n$ and $\mathbb{V}_{\rm U}[T_n] \sim 5.050 \cdot 1.822^n$, respectively. Under the Yule model, which assigns higher probabilities to more balanced labeled topologies, we obtain the mean $\mathbb{E}_{\rm Y}[T_n] \sim 1.425^n$ and the variance $\mathbb{V}_{\rm Y}[T_n] \sim 2.045^n$.

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks in which every reticulation node has exactly two parents. We extend these studies to $d$-combining tree-child networks where every reticulation node has now $d\geq 2$ parents, and we study one-component as well as general tree-child networks. For the number of one-component networks, we derive an exact formula from which asymptotic results follow that contain a stretched exponential for $d=2$, yet not for $d \geq 3$. For general networks, we find a novel encoding by words which leads to a recurrence for their numbers. From this recurrence, we derive asymptotic results which show the appearance of a stretched exponential for all $d \geq 2$. Moreover, we also give results on the distribution of shape parameters (e.g., number of reticulation nodes, Sackin index) of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves. We show phase transitions depending on $d$, leading to normal, Bessel, Poisson, and degenerate distributions. Some of our results are new even in the bicombining case., Comment: Revised version; accepted for publication in Adv. in Appl. Math

The Yule branching process is a classical model for the random generation of gene tree topologies in population genetics. It generates binary ranked trees -- also called "histories" -- with a finite number $n$ of leaves. We study the lengths $\ell_1 > \ell_2 > ... > \ell_k > ...$ of the external branches of a Yule generated random history of size $n$, where the length of an external branch is defined as the rank of its parent node. When $n \rightarrow \infty$, we show that the random variable $\ell_k$, once rescaled as $\frac{n-\ell_k}{\sqrt{n/2}}$, follows a $\chi$-distribution with $2k$ degrees of freedom, with mean $\mathbb E(\ell_k) \sim n$ and variance $\mathbb V(\ell_k) \sim n \big(k-\frac{\pi k^2}{16^k} \binom{2k}{k}^2\big)$. Our results contribute to the study of the combinatorial features of Yule generated gene trees, in which external branches are associated with singleton mutations affecting individual gene copies.

We prove limit laws for the number of occurrences of a pattern on the fringe of a ranked tree-child network which is picked uniformly at random. Our results extend the limit law for cherries proved by Bienvenu et al. (2022). For patterns of height $1$ and $2$, we show that they either occur frequently (mean is asymptotically linear and limit law is normal) or sporadically (mean is asymptotically constant and limit law is Poisson) or not all (mean tends to $0$ and limit law is degenerate). We expect that these are the only possible limit laws for any fringe pattern., Comment: 20 pages

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for {\it bicombining tree-child networks} which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to {\it $d$-combining tree-child networks} where every reticulation node has now $d\geq 2$ parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves., Comment: Extended abstract which is accepted for presentation at AofA2022; an accompanying Maple worksheet can be found in the ancillary file folder

The Sackin and Colless indices are two widely-used metrics for measuring the balance of trees and for testing evolutionary models in phylogenetics. This short paper contributes two results about the Sackin and Colless indices of trees. One result is the asymptotic analysis of the expected Sackin and Colless indices of a tree shape (which are full binary rooted unlabelled trees) under the uniform model where tree shapes are sampled with equal probability. Another is a short elementary proof of the closed formula for the expected Sackin index of phylogenetic trees (which are full binary rooted trees with leaves being labelled with taxa) under the uniform model., Comment: 10 pages, 1 fugre

Tree-child networks are an important network class which are used in phylogenetics to model reticulate evolution. In a recent paper, Pons and Batle (2021) conjectured a relation between tree-child networks and certain words. In this short note, we prove their conjecture for the (important) class of one-component tree-child networks., Comment: 6 pages

The class of ranked tree-child networks, tree-child networks arising from an evolution process with a fixed embedding into the plane, has recently been introduced by Bienvenu, Lambert, and Steel. These authors derived counting results for this class. In this note, we will give bijective proofs of three of their results. Two of our bijections answer questions raised in their paper., Comment: revised version, 12 pages, 13 Figures

Tree-child networks, one of the prominent network classes in phylogenetics, have been introduced for the purpose of modeling reticulate evolution. Recently, the first author together with Gittenberger and Mansouri (2019) showed that the number ${\rm TC}_{\ell,k}$ of tree-child networks with $\ell$ leaves and $k$ reticulation vertices has the first-order asymptotics \[ {\rm TC}_{\ell,k}\sim c_k\left(\frac{2}{e}\right)^{\ell}\ell^{\ell+2k-1},\qquad (\ell\rightarrow\infty). \] Moreover, they also computed $c_k$ for $k=1,2,$ and $3$. In this short note, we give a second approach to the above result which is based on a recent (algorithmic) approach for the counting of tree-child networks due to Cardona and Zhang (2020). This second approach is also capable of giving a simple, closed-form expression for $c_k$, namely, $c_k=2^{k-1}\sqrt{2}/k!$ for all $k\geq 0$., Comment: accepted version, 13 pages