50 Result(s)
within
David Fernández-Baca
-
Chapter and Conference Paper
Fast Local Search for Unrooted Robinson-Foulds Supertrees
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
Constructing Large Conservative Supertrees
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...
-
Article
Open AccessiGTP: A software package for large-scale gene tree parsimony analysis
The ever-increasing wealth of genomic sequence information provides an unprecedented opportunity for large-scale phylogenetic analysis. However, species phylogeny inference is obfuscated by incongruence among ...
-
Article
Open AccessRobinson-Foulds Supertrees
Supertree methods synthesize collections of small phylogenetic trees with incomplete taxon overlap into comprehensive trees, or supertrees, that include all taxa found in the input trees. Supertree methods bas...
-
Article
Open AccessConstructing majority-rule supertrees
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
Constructing Majority-Rule Supertrees
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
Generalized Binary Tanglegrams: Algorithms and Applications
Several applications require the joint display of two phylogenetic trees whose leaves are matched by inter-tree edges. This issue arises, for example, when comparing gene trees and species trees or when studyi...
-
Article
Open AccessPhyloFinder: An intelligent search engine for phylogenetic tree databases
Bioinformatic tools are needed to store and access the rapidly growing phylogenetic data. These tools should enable users to identify existing phylogenetic trees containing a specified taxon or set of taxa and...
-
Chapter and Conference Paper
Comparing and Aggregating Partially Resolved Trees
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
Parametric Analysis for Ungapped Markov Models of Evolution
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
MRF Supertrees
We survey and present new results and techniques for the supertree method matrix representation using flip** (MRF). The method resolves inconsistencies among the input trees by working with the matrix represent...
-
Chapter and Conference Paper
Supertrees by Flip**
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
Inverse Parametric Sequence Alignment
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
The Perfect Phylogeny Problem
A phylogeny is a tree representation of the evolutionary history of a set of taxa (organisms, biological sequences, populations, or languages). Thus, phylogeny construction is among the basic computational proble...
-
Chapter and Conference Paper
Multi-parameter Minimum Spanning Trees
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
Parametric Multiple Sequence Alignment and Phylogeny Construction
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
Faster non-linear parametric search with applications to optimization and dynamic geometry
A technique for accelerating certain applications of parametric search to non-linear problems is presented, together with its applications to optimization on weighted graphs and to two problems in dynamic geom...
-
Chapter and Conference Paper
A polynomial-time algorithm for near-perfect phylogeny
We define a parameterized version of the Steiner tree problem in phylogeny where the parameter measures the amount by which a phylogeny differs from “perfection.” This problem is shown to be solvable in polyno...
-
Chapter and Conference Paper
On the approximability of the Steiner tree problem in phylogeny
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
Using sparsification for parametric minimum spanning tree problems
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...
