The Asymptotic Distribution of the k -Robinson–Foulds Dissimilarity Measure on Labeled Trees

Abstract

Motivated by applications in medical bioinformatics, Khayatian et al. (2024) introduced a family of metrics on Cayley trees [the k-Robinson–Foulds (RF) distance, for $\mathit{k}\hspace{0.17em}\mathbf{=}\hspace{0.17em}0\mathbf{,}$  . . .  $,\mathit{n}\mathbf{-}2$ ] and explored their distribution on pairs of random Cayley trees via simulations. In this article, we investigate this distribution mathematically and derive exact asymptotic descriptions of the distribution of the k-RF metric for the extreme values $\mathit{k}\hspace{0.17em}\mathbf{=}\hspace{0.17em}0$ and $\mathit{k}\hspace{0.17em}\mathbf{=}\hspace{0.17em}\mathit{n}\mathbf{-}2$ , as n becomes large. We show that a linear transform of the 0-RF metric converges to a Poisson distribution (with mean 2), whereas a similar transform for the ( $\mathit{n}\mathbf{-}2$ )-RF metric leads to a normal distribution (with mean $\sim \hspace{0.17em}\mathit{n}{\mathit{e}}^{\mathbf{-}2}$ ). These results (together with the case $\mathit{k}\hspace{0.17em}\mathbf{=}\hspace{0.17em}1$ which behaves quite differently and $\mathit{k}\hspace{0.17em}\mathbf{=}\hspace{0.17em}\mathit{n}\mathbf{-}3$ ) shed light on the earlier simulation results and the predictions made concerning them.