اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHow tree-based is my network? Proximity measures for unrooted phylogenetic networks
121
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Tree-based networks are a class of phylogenetic networks that attempt to formally capture what is meant by tree-like evolution. A given non-tree-based phylogenetic network, however, might appear to be very close to being tree-based, or very far. In this paper, we formalise the notion of proximity to tree-based for unrooted phylogenetic networks, with a range of proximity measures. These measures also provide characterisations of tree-based networks. One measure in particular, related to the nearest neighbour interchange operation, allows us to define the notion of tree-based rank. This provides a subclassification within the tree-based networks themselves, identifying those networks that are very tree-based. Finally, we prove results relating tree-based networks in the settings of rooted and unrooted phylogenetic networks, showing effectively that an unrooted network is tree-based if and only if it can be made a rooted tree-based network by rooting it and orienting the edges appropriately. This leads to a clarification of the contrasting decision problems for tree-based networks, which are polynomial in the rooted case but NP complete in the unrooted.
قيم البحث
اقرأ أيضاً
Phylogenetic networks are a generalization of phylogenetic trees allowing for the representation of non-treelike evolutionary events such as hybridization. Typically, such networks have been analyzed based on their `level, i.e. based on the complexit
y of their 2-edge-connected components. However, recently the question of how `treelike a phylogenetic network is has become the center of attention in various studies. This led to the introduction of emph{tree-based networks}, i.e. networks that can be constructed from a phylogenetic tree, called the emph{base tree}, by adding additional edges. While the concept of tree-basedness was originally introduced for rooted phylogenetic networks, it has recently also been considered for unrooted networks. In the present study, we compare and contrast findings obtained for unrooted emph{binary} tree-based networks to unrooted emph{non-binary} networks. In particular, while it is known that up to level 4 all unrooted binary networks are tree-based, we show that in the case of non-binary networks, this result only holds up to level 3.
Phylogenetic networks are generalizations of phylogenetic trees that allow the representation of reticulation events such as horizontal gene transfer or hybridization, and can also represent uncertainty in inference. A subclass of these, tree-based p
hylogenetic networks, have been introduced to capture the extent to which reticulate evolution nevertheless broadly follows tree-like patterns. Several important operations that change a general phylogenetic network have been developed in recent years, and are important for allowing algorithms to move around spaces of networks; a vital ingredient in finding an optimal network given some biological data. A key such operation is the Nearest Neighbor Interchange, or NNI. While it is already known that the space of unrooted phylogenetic networks is connected under NNI, it has been unclear whether this also holds for the subspace of tree-based networks. In this paper we show that the space of unrooted tree-based phylogenetic networks is indeed connected under the NNI operation. We do so by explicitly showing how to get from one such network to another one without losing tree-basedness along the way. Moreover, we introduce some new concepts, for instance ``shoat networks, and derive some interesting aspects concerning tree-basedness. Last, we use our results to derive an upper bound on the size of the space of tree-based networks.
A tree-based network $N$ on $X$ is called universal if every phylogenetic tree on $X$ is a base tree for $N$. Recently, binary universal tree-based networks have attracted great attention in the literature and their existence has been analyzed in var
ious studies. In this note, we extend the analysis to non-binary networks and show that there exist both a rooted and an unrooted non-binary universal tree-based network with $n$ leaves for all positive integers $n$.
Phylogenetic Diversity (PD) is a prominent quantitative measure of the biodiversity of a collection of present-day species (taxa). This measure is based on the evolutionary distance among the species in the collection. Loosely speaking, if $mathcal{T
}$ is a rooted phylogenetic tree whose leaf set $X$ represents a set of species and whose edges have real-valued lengths (weights), then the PD score of a subset $S$ of $X$ is the sum of the weights of the edges of the minimal subtree of $mathcal{T}$ connecting the species in $S$. In this paper, we define several natural variants of the PD score for a subset of taxa which are related by a known rooted phylogenetic network. Under these variants, we explore, for a positive integer $k$, the computational complexity of determining the maximum PD score over all subsets of taxa of size $k$ when the input is restricted to different classes of rooted phylogenetic networks
Rooted phylogenetic networks provide a way to describe species relationships when evolution departs from the simple model of a tree. However, networks inferred from genomic data can be highly tangled, making it difficult to discern the main reticulat
ion signals present. In this paper, we describe a natural way to transform any rooted phylogenetic network into a simpler canonical network, which has desirable mathematical and computational properties, and is based only on the visible nodes in the original network. The method has been implemented and we demonstrate its application to some examples.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
