LATIN 2012: Theoretical Informatics
10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings
Article
We present a new graph-based approach to the following basic problem in phylogenetic tree construction. Let $$\mathcal {P}= \{T_1, \ld...
Chapter and Conference Paper
Semi-labeled trees are phylogenies whose internal nodes may be labeled by higher-order taxa. Thus, a leaf labeled Mus musculus could nest within a subtree whose root node is labeled Rodentia, which itself could n...
Article
Chapter and Conference Paper
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 ...
Book and Conference Proceedings
10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings
Chapter and Conference Paper
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 co...
Chapter and Conference Paper
We study the agreement supertree approach for combining rooted phylogenetic trees when the input trees do not fully agree on the relative positions of the taxa. Two approaches to dealing with such conflicting ...
Chapter and Conference Paper
A rogue taxon in a collection of phylogenetic trees is one whose position varies drastically from tree to tree. The presence of such taxa can greatly reduce the resolution of the consensus tree (e.g., the majo...
Chapter and Conference Paper
A multi-labeled tree, or MUL-tree, is a phylogenetic tree where two or more leaves share a label, e.g., a species name. A MUL-tree can imply multiple conflicting phylogenetic relationships for the same set of ...
Chapter and Conference Paper
A Robinson-Foulds (RF) supertree for a collection of input trees is a comprehensive species phylogeny that is at minimum total RF distance to the input trees. Thus, an RF supertree is consistent with the maxim...
Chapter and Conference Paper
Generalizations of the strict and loose consensus methods to the supertree setting, recently introduced by McMorris and Wilkinson, are studied. The supertrees these methods produce are conservative in the sens...
Chapter and Conference Paper
Supertree methods combine the phylogenetic information from multiple partially-overlap** trees into a larger phylogenetic tree called a supertree. Several supertree construction methods have been proposed to...
Chapter and Conference Paper
We define, analyze, and give efficient algorithms for two kinds of distance measures for rooted and unrooted phylogenies. For rooted trees, our measures are based on the topologies the input trees induce on tripl...
Chapter and Conference Paper
We present efficient sensitivity-analysis algorithms for two problems involving Markov models of sequence evolution: ancestral reconstruction in evolutionary trees and local ungapped alignment under log-odds s...
Chapter and Conference Paper
The input to a supertree problem is a collection of phyloge-netic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in...
Chapter and Conference Paper
We consider the inverse parametric sequence alignment problem, where a sequence alignment is given and the task is to determine parameter values such that the given alignment is optimal at that parameter setti...
Chapter and Conference Paper
A framework for solving certain multidimensional parametric search problems in randomized linear time is presented, along with its application to optimization on matroids, including parametric minimum spanning...
Chapter and Conference Paper
Bounds are given on the size of the parameter-space decomposition induced by multiple sequence alignment problems where phylogenetic information may be given or inferred. It is shown that many of the usual for...
Chapter and Conference Paper
Three results on the Steiner tree problem are presented: (i) Computing optimum k-restricted Steiner tree is APX-complete for k≥4, (ii) the minimum-cost k-restricted Steiner tree problem in phylogeny is APX-comple...
Chapter and Conference Paper
Two applications of sparsification to parametric computing are given. The first is a fast algorithm for enumerating all distinct minimum spanning trees in a graph whose edge weights vary linearly with a parame...