اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCombinatorial and stochastic properties of ranked tree-child networks
76
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Tree-child networks are a recently-described class of directed acyclic graphs that have risen to prominence in phylogenetics (the study of evolutionary trees and networks). Although these networks have a number of attractive mathematical properties, many combinatorial questions concerning them remain intractable. In this paper, we show that endowing these networks with a biologically relevant ranking structure yields mathematically tractable objects, which we term ranked tree-child networks (RTCNs). We explain how to derive exact and explicit combinatorial results concerning the enumeration and generation of these networks. We also explore probabilistic questions concerning the properties of RTCNs when they are sampled uniformly at random. These questions include the lengths of random walks between the root and leaves (both from the root to the leaves and from a leaf to the root); the distribution of the number of cherries in the network; and sampling RTCNs conditional on displaying a given tree. We also formulate a conjecture regarding the scaling limit of the process that counts the number of lineages in the ancestry of a leaf. The main idea in this paper, namely using ranking as a way to achieve combinatorial tractability, may also extend to other classes of networks.
قيم البحث
اقرأ أيضاً
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.
Phylogenetic trees canonically arise as embeddings of phylogenetic networks. We recently showed that the problem of deciding if two phylogenetic networks embed the same sets of phylogenetic trees is computationally hard, blue{in particular, we showed
it to be $Pi^P_2$-complete}. In this paper, we establish a polynomial-time algorithm for this decision problem if the initial two networks consists of a normal network and a tree-child network. The running time of the algorithm is quadratic in the size of the leaf sets.
It is well known that excessive harvesting or hunting has driven species to extinction both on local and global scales. This leads to one of the fundamental problems of conservation ecology: how should we harvest a population so that economic gain is
maximized, while also ensuring that the species is safe from extinction? We study an ecosystem of interacting species that are influenced by random environmental fluctuations. At any point in time, we can either harvest or seed (repopulate) species. Harvesting brings an economic gain while seeding incurs a cost. The problem is to find the optimal harvesting-seeding strategy that maximizes the expected total income from harvesting minus the cost one has to pay for the seeding of various species. We consider what happens when one, or both, of the seeding and harvesting rates are bounded. The focus of this paper is the analysis of these three novel settings: bounded seeding and infinite harvesting, bounded seeding and bounded harvesting, and infinite seeding and bounded harvesting. We prove analytical results and develop numerical approximation methods. By implementing these approximations, we are able to gain qualitative information about how to best harvest and seed species. We are able to show that in the single species setting there are thresholds $0<L_1<L_2<infty$ such that: 1) if the population size is `low, so that it lies in $(0, L_1]$, there is seeding using the maximal seeding rate; 2) if the population size `moderate, so that it lies in $(L_1,L_2)$, there is no harvesting or seeding; 3) if the population size is `high, so that it lies in the interval $[L_2, infty)$, there is harvesting using the maximal harvesting rate. Once we have a system with at least two species, numerical experiments show that constant threshold strategies are not optimal anymore.
For each $n ge 1$, let $mathrm{d}^n=(d^{n}(i),1 le i le n)$ be a sequence of positive integers with even sum $sum_{i=1}^n d^n(i) ge 2n$. Let $(G_n,T_n,Gamma_n)$ be uniformly distributed over the set of simple graphs $G_n$ with degree sequence $mathrm
{d}^n$, endowed with a spanning tree $T_n$ and rooted along an oriented edge $Gamma_n$ of $G_n$ which is not an edge of $T_n$. Under a finite variance assumption on degrees in $G_n$, we show that, after rescaling, $T_n$ converges in distribution to the Brownian continuum random tree as $n to infty$. Our main tool is a new version of Pitmans additive coalescent (https://doi.org/10.1006/jcta.1998.2919), which can be used to build both random trees with a fixed degree sequence, and random tree-weighted graphs with a fixed degree sequence. As an input to the proof, we also derive a Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed graph and a random graph with a given degree sequence sampled according to the configuration model; we find this to be of independent interest.
Phylogenetic diversity indices provide a formal way to apportion evolutionary heritage across species. Two natural diversity indices are Fair Proportion (FP) and Equal Splits (ES). FP is also called evolutionary distinctiveness and, for rooted trees,
is identical to the Shapley Value (SV), which arises from cooperative game theory. In this paper, we investigate the extent to which FP and ES can differ, characterise tree shapes on which the indices are identical, and study the equivalence of FP and SV and its implications in more detail. We also define and investigate analogues of these indices on unrooted trees (where SV was originally defined), including an index that is closely related to the Pauplin representation of phylogenetic diversity.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
