30 research outputs found
Some Problems Related to the Space of Optimal Tree Reconciliations (Invited Talk)
No full textTree reconciliation is a general framework for investigating the evolution of strongly dependent systems as hosts and parasites or genes and species, based on their phylogenetic information. Indeed, informally speaking, it reconciles any differences between two phylogenetic trees by means of biological events. Tree reconciliation is usually computed according to the parsimony principle, that is, to each evolutionary event a cost is assigned and the goal is to find tree reconciliations of minimum total cost. Unfortunately, the number of optimal reconciliations is usually huge and many biological applications require to enumerate and to examine all of them, so it is necessary to handle them. In this paper we list some problems connected with the management of such a big space of tree reconciliations and, for each of them, discuss some known solutions
On Graphs that are not Star-K-PCGs (short paper)
No full textA graph G is a star-k-PCG if there exists a non-negative edge weighted star tree S and k mutually exclusiveintervals I_1,I_2,...,I_k of non-negative reals such that each vertex of -g corresponds to a leaf of S and there is an edge between two vertices in G if the distance between their corresponding leaves in S lies in the union of these intervals. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. In this paper, we investigate the smallest value of n such that there exists an n vertex graph that is not a star-k-PCG, for small values of k
Rainbow graph splitting
No full textGiven an integer c, an edge colored graph G is said to be rainbow c-splittable if it can be decomposed into at most c vertex-disjoint monochromatic induced subgraphs of distinct colors. We provide a polynomial-time algorithm for deciding whether an edge-colored complete graph is rainbow c-splittable. For not necessarily complete graphs, we show that the problem is polynomial if c = 2, whereas for c >= 3 it is NP-complete even if the graph has maximum degree 2c - 1. Finally, it remains NP-complete even for 2-edge colored graphs of maximum degree 7c - 14. (C) 2011 Elsevier B.V. All rights reserved
Comparing related phylogenetic trees
No full textIn phylogenetics, several classical distances exist to compare two phylogenetic trees. However, when the evolution in one tree has been influenced by the evolution in the other (e.g. two ecologically linked groups of organisms as hosts and their symbionts), other methods are more appropriate to compare the trees. Among the most used ones, there is phylogenetic tree reconciliation, i.e. mapping of one tree into the other according to certain rules, with a quantification of its quality; we refer to distances based on this concept as reconciliation distances. They bring useful information but are unfortunately NP-hard to be computed. It is then interesting to understand whether a polynomial phylogenetic tree distance is correlated to the reconciliation distances. In this communication we announce a systematic study to compare clas- sical and reconciliation distances and we show that there is not much correlation between them. We then introduce a new distance that is in- stead correlated with the reconciliation distances and can be computed in polynomial time, hence it represents an efficient alternative to them
Pairwise compatibility graphs: A survey
No full textA graph G = (V, E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two nonnegative real numbers dmin and dmax such that each leaf u of T is a node of V and there is an edge (u, v) ∈ E if and only if dmin ≤ dT (u, v) ≤ dmax, where dT (u, v) is the sum of weights of the edges on the unique path from u to v in T. In this article, we survey the state of the art concerning this class of graphs and some of its subclasses
On the Domination Number of t-Constrained de Bruijn Graphs (Short Paper)
No full textMotivated by the work on the domination number of de Bruijn graphs and some of its generalizations, we introduce a natural generalization of de Bruijn graphs (directed and undirected), namely t-constrained de Bruijn graphs, where t is a positive integer, and then study the domination number of these graphs. Within the definition of t-constrained de Bruijn graphs, de Bruijn and Kautz graphs correspond to 1-constrained and 2-constrained de Bruijn graphs, respectively. This generalization inherits many structural properties of de Bruijn graphs and may have similar applications in interconnection networks or bioinformatics. We establish upper and lower bounds for the domination number on t-constrained de Bruijn graphs both in the directed and in the undirected case. These bounds are often very close and in some cases we are able to find the exact value
On cancellative set families
No full textA family of subsets of an n-set is 2-cancellative if, for every four-tuple {A,B, C,D} of its members, A∪B∪C=A∪B∪D implies C=D. This generalizes the concept of cancellative set families, defined by the property that A∪B ≠ A∪C for A, B, C all different. The asymptotics of the maximum size of cancellative families of subsets of an n-set is known (Tolhuizen [7]). We provide a new upper bound on the size of 2-cancellative families, improving the previous bound of 20.458n to 20.42n
All graphs with at most seven vertices are Pairwise compatibility graphs
No full textA graph G is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular, all these graphs except for the wheel on seven vertices W 7 are PCGs of a particular structure of a tree: a centipede. © 2012 The Author 2012. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved
Pairwise Compatibility Graphs of Caterpillars
No full textA graph G = (V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u of V and there is an edge (u, v) in E if and only if dmin <= dT,w(lu, lv) <= dmax where dT,w(lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n = 7, ... , 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any pairwise compatibility graph admits a full binary tree as witness tree T
Cophylogeny reconstruction via an approximate bayesian computation
No full textDespite an increasingly vast literature on cophylogenetic reconstructions for studying host-parasite associations, understanding the common evolutionary history of such systems remains a problem that is far from being solved. Most algorithms for host-parasite reconciliation use an event-based model, where the events include in general (a subset of) cospeciation, duplication, loss, and host switch. All known parsimonious event-based methods then assign a cost to each type of event in order to find a reconstruction of minimum cost. The main problem with this approach is that the cost of the events strongly influences the reconciliation obtained. Some earlier approaches attempt to avoid this problem by finding a Pareto set of solutions and hence by considering event costs under some minimization constraints. To deal with this problem, we developed an algorithm, called Coala, for estimating the frequency of the events based on an approximate Bayesian computation approach. The benefits of this method are 2-fold: (i) it provides more confidence in the set of costs to be used in a reconciliation, and (ii) it allows estimation of the frequency of the events in cases where the data set consists of trees with a large number of taxa. We evaluate our method on simulated and on biological data sets. We show that in both cases, for the same pair of host and parasite trees, different sets of frequencies for the events lead to equally probable solutions. Moreover, often these solutions differ greatly in terms of the number of inferred events. It appears crucial to take this into account before attempting any further biological interpretation of such reconciliations. More generally, we also show that the set of frequencies can vary widely depending on the input host and parasite trees. Indiscriminately applying a standard vector of costs may thus not be a good strategy
