Source author record

Sudheer Vakati

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Computational Engineering, Finance, and Science Data Structures and Algorithms math.CO Quantitative Methods

Catalog footprint

Research overview

4works

5topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Characterizing Compatibility and Agreement of Unrooted Trees via Cuts in Graphs

Deciding whether there is a single tree -a supertree- that summarizes the evolutionary information in a collection of unrooted trees is a fundamental problem in phylogenetics. We consider two versions of this question: agreement and compatibility. In the first, the supertree is required to reflect precisely the relationships among the species exhibited by the input trees. In the second, the supertree can be more refined than the input trees. Tree compatibility can be characterized in terms of the existence of a specific kind of triangulation in a structure known as the display graph. Alternatively, it can be characterized as a chordal graph sandwich problem in a structure known as the edge label intersection graph. Here, we show that the latter characterization yields a natural characterization of compatibility in terms of minimal cuts in the display graph, which is closely related to compatibility of splits. We then derive a characterization for agreement.

preprint2012arXiv

Improved Lower Bounds on the Compatibility of Multi-State Characters

We study a long standing conjecture on the necessary and sufficient conditions for the compatibility of multi-state characters: There exists a function $f(r)$ such that, for any set $C$ of $r$ -state characters, $C$ is compatible if and only if every subset of $f(r)$ characters of $C$ is compatible. We show that for every $r \ge 2$ , there exists an incompatible set $C$ of $\lfloor\frac{r}{2}\rfloor\cdot\lceil\frac{r}{2}\rceil + 1$ $r$ -state characters such that every proper subset of $C$ is compatible. Thus, $f(r) \ge \lfloor\frac{r}{2}\rfloor\cdot\lceil\frac{r}{2}\rceil + 1$ for every $r \ge 2$ . This improves the previous lower bound of $f(r) \ge r$ given by Meacham (1983), and generalizes the construction showing that $f(4) \ge 5$ given by Habib and To (2011). We prove our result via a result on quartet compatibility that may be of independent interest: For every integer $n \ge 4$ , there exists an incompatible set $Q$ of $\lfloor\frac{n-2}{2}\rfloor\cdot\lceil\frac{n-2}{2}\rceil + 1$ quartets over $n$ labels such that every proper subset of $Q$ is compatible. We contrast this with a result on the compatibility of triplets: For every $n \ge 3$ , if $R$ is an incompatible set of more than $n-1$ triplets over $n$ labels, then some proper subset of $R$ is incompatible. We show this upper bound is tight by exhibiting, for every $n \ge 3$ , a set of $n-1$ triplets over $n$ taxa such that $R$ is incompatible, but every proper subset of $R$ is compatible.

preprint2012arXiv

On Two Graph-Theoretic Characterizations of Tree Compatibility

Deciding whether a collection of unrooted trees is compatible is a fundamental problem in phylogenetics. Two different graph-theoretic characterizations of tree compatibility have recently been proposed. In one of these, tree compatibility is characterized in terms of the existence of a specific kind of triangulation in a structure known as the display graph. An alternative characterization expresses the tree compatibility problem as a chordal graph sandwich problem in a structure known as the edge label intersection graph. In this paper we show that the characterization using edge label intersection graphs transforms to a characterization in terms of minimal cuts of the display graph. We show how these two characterizations are related to compatibility of splits. We also show how the characterization in terms of minimal cuts of display graph is related to the characterization in terms of triangulation of the display graph.

preprint2010arXiv

Graph Triangulations and the Compatibility of Unrooted Phylogenetic Trees

We characterize the compatibility of a collection of unrooted phylogenetic trees as a question of determining whether a graph derived from these trees --- the display graph --- has a specific kind of triangulation, which we call legal. Our result is a counterpart to the well known triangulation-based characterization of the compatibility of undirected multi-state characters.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.