اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCombinatorial perspectives on Dollo-$k$ characters in phylogenetics
61
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Recently, the perfect phylogeny model with persistent characters has attracted great attention in the literature. It is based on the assumption that complex traits or characters can only be gained once and lost once in the course of evolution. Here, we consider a generalization of this model, namely Dollo parsimony, that allows for multiple character losses. More precisely, we take a combinatorial perspective on the notion of Dollo-$k$ characters, i.e. traits that are gained at most once and lost precisely $k$ times throughout evolution. We first introduce an algorithm based on the notion of spanning subtrees for finding a Dollo-$k$ labeling for a given character and a given tree in linear time. We then compare persistent characters (consisting of the union of Dollo-0 and Dollo-1 characters) and general Dollo-$k$ characters. While it is known that there is a strong connection between Fitch parsimony and persistent characters, we show that Dollo parsimony and Fitch parsimony are in general very different. Moreover, while it is known that there is a direct relationship between the number of persistent characters and the Sackin index of a tree, a popular index of tree balance, we show that this relationship does not generalize to Dollo-$k$ characters. In fact, determining the number of Dollo-$k$ characters for a given tree is much more involved than counting persistent characters, and we end this manuscript by introducing a recursive approach for the former. This approach leads to a polynomial time algorithm for counting the number of Dollo-$k$ characters, and both this algorithm as well as the algorithm for computing Dollo-$k$ labelings are publicly available in the Babel package for BEAST 2.
قيم البحث
اقرأ أيضاً
Recently several minimum free energy (MFE) folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Their folding targets are interaction structures, that can be represented as diagrams with two backb
ones drawn horizontally on top of each other such that (1) intramolecular and intermolecular bonds are noncrossing and (2) there is no zig-zag configuration. This paper studies joint structures with arc-length at least four in which both, interior and exterior stack-lengths are at least two (no isolated arcs). The key idea in this paper is to consider a new type of shape, based on which joint structures can be derived via symbolic enumeration. Our results imply simple asymptotic formulas for the number of joint structures with surprisingly small exponential growth rates. They are of interest in the context of designing prediction algorithms for RNA-RNA interactions.
We apply down operators in the affine nilCoxeter algebra to yield explicit combinatorial expansions for certain families of non-commutative k-Schur functions. This yields a combinatorial interpretation for a new family of k-Littlewood-Richardson coefficients.
The human microbiome is the ensemble of genes in the microbes that live inside and on the surface of humans. Because microbial sequencing information is now much easier to come by than phenotypic information, there has been an explosion of sequencing
and genetic analysis of microbiome samples. Much of the analytical work for these sequences involves phylogenetics, at least indirectly, but methodology has developed in a somewhat different direction than for other applications of phylogenetics. In this paper I review the field and its methods from the perspective of a phylogeneticist, as well as describing current challenges for phylogenetics coming from this type of work.
Let $Q_{n,d}$ denote the random combinatorial matrix whose rows are independent of one another and such that each row is sampled uniformly at random from the subset of vectors in ${0,1}^n$ having precisely $d$ entries equal to $1$. We present a short
proof of the fact that $Pr[det(Q_{n,d})=0] = Oleft(frac{n^{1/2}log^{3/2} n}{d}right)=o(1)$, whenever $d=omega(n^{1/2}log^{3/2} n)$. In particular, our proof accommodates sparse random combinatorial matrices in the sense that $d = o(n)$ is allowed. We also consider the singularity of deterministic integer matrices $A$ randomly perturbed by a sparse combinatorial matrix. In particular, we prove that $Pr[det(A+Q_{n,d})=0]=Oleft(frac{n^{1/2}log^{3/2} n}{d}right)$, again, whenever $d=omega(n^{1/2}log^{3/2} n)$ and $A$ has the property that $(1,-d)$ is not an eigenpair of $A$.
In the study of rooted phylogenetic networks, analyzing the set of rooted phylogenetic trees that are embedded in such a network is a recurring task. From an algorithmic viewpoint, this analysis almost always requires an exhaustive search of a partic
ular multiset $S$ of rooted phylogenetic trees that are embedded in a rooted phylogenetic network $mathcal{N}$. Since the size of $S$ is exponential in the number of reticulations of $mathcal{N}$, it is consequently of interest to keep this number as small as possible but without loosing any element of $S$. In this paper, we take a first step towards this goal by introducing the notion of a non-essential arc of $mathcal{N}$, which is an arc whose deletion from $mathcal{N}$ results in a rooted phylogenetic network $mathcal{N}$ such that the sets of rooted phylogenetic trees that are embedded in $mathcal{N}$ and $mathcal{N}$ are the same. We investigate the popular class of tree-child networks and characterize which arcs are non-essential. This characterization is based on a family of directed graphs. Using this novel characterization, we show that identifying and deleting all non-essential arcs in a tree-child network takes time that is cubic in the number of leaves of the network. Moreover, we show that deciding if a given arc of an arbitrary phylogenetic network is non-essential is $Pi_2^P$-complete.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
