LATIN 2012: Theoretical Informatics
10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings
Page
%P
50 Result(s)
within
David Fernández-Baca
English
-
Article
Open AccessTesting the agreement of trees with internal labels
A semi-labeled tree is a tree where all leaves as well as, possibly, some internal nodes are labeled with taxa. Semi-labeled trees encompass ordinary phylogenetic trees and taxonomies. Suppose we are given a c...
-
Chapter and Conference Paper
Testing the Agreement of Trees with Internal Labels
The input to the agreement problem is a collection \(\mathcal {P}= \{\mathcal {T}_1, \mathcal {T}_2, \dots , \mathcal {T}_k\}\) of phylogenetic trees, called input trees, over partially overlap** sets of taxa...
-
Chapter and Conference Paper
Checking Phylogenetic Decisiveness in Theory and in Practice
Suppose we have a set X consisting of n taxa and we are given information from k loci from which to construct a phylogeny for X. Each locus offers information for only a fraction of the taxa. The question is whet...
-
Article
Fast Compatibility Testing for Rooted Phylogenetic Trees
We present a new graph-based approach to the following basic problem in phylogenetic tree construction. Let $$\mathcal {P}= \{T_1, \ld...
-
Article
Open AccessAn efficient algorithm for testing the compatibility of phylogenies with nested taxa
Semi-labeled trees generalize ordinary phylogenetic trees, allowing internal nodes to be labeled by higher-order taxa. Taxonomies are examples of semi-labeled trees. Suppose we are given collection ...
-
Chapter and Conference Paper
Fast Compatibility Testing for Phylogenies with Nested Taxa
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...
-
Chapter and Conference Paper
Constructing and Employing Tree Alignment Graphs for Phylogenetic Synthesis
Tree alignment graphs (TAGs) provide an intuitive data structure for storing phylogenetic trees that exhibits the relationships of the individual input trees and can potentially account for nested taxonomic re...
-
Article
EvoMiner: frequent subtree mining in phylogenetic databases
The problem of mining collections of trees to identify common patterns, called frequent subtrees (FSTs), arises often when trying to interpret the results of phylogenetic analysis. FST mining generalizes the w...
-
Article
Editorial
-
Article
Open AccessEnumerating all maximal frequent subtrees in collections of phylogenetic trees
A common problem in phylogenetic analysis is to identify frequent patterns in a collection of phylogenetic trees. The goal is, roughly, to find a subset of the species (taxa) on which all or some significant s...
-
Article
Open AccessCharacterizing 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 ...
-
Article
Open AccessInferring species trees from incongruent multi-copy gene trees using the Robinson-Foulds distance
Constructing species trees from multi-copy gene trees remains a challenging problem in phylogenetics. One difficulty is that the underlying genes can be incongruent due to evolutionary processes such as gene d...
-
Article
Open AccessExtracting conflict-free information from multi-labeled trees
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 ...
-
Article
Open AccessIncompatible quartets, triplets, and 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 co...
-
Chapter and Conference Paper
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 ...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Improved Lower Bounds on the Compatibility of Quartets, Triplets, and 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 co...
-
Chapter and Conference Paper
Fixed-Parameter Algorithms for Finding Agreement Supertrees
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
Identifying Rogue Taxa through Reduced Consensus: NP-Hardness and Exact Algorithms
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
Extracting Conflict-Free Information from Multi-labeled Trees
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 ...
