The complexity of reconstructing trees from qualitative characters and subtrees
From MaRDI portal
Publication:1203103
DOI10.1007/BF02618470zbMath0766.92002MaRDI QIDQ1203103
Publication date: 4 February 1993
Published in: Journal of Classification (Search for Journal in Brave)
algorithmcomputational complexityclustersNP-completepolynomial timecompatibilityrooted treesunrooted treesstrict consensus treeoverlapping sets of labelsparent treespartial binary charactersqualitative charactersresolved quartetsrooted subtreestree-like classifications
Analysis of algorithms and problem complexity (68Q25) Taxonomy, cladistics, statistics in mathematical biology (92B10)
Related Items
On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters ⋮ Consistency and inconsistency of consensus methods for inferring species trees from gene trees in the presence of ancestral population structure ⋮ Compatibility of unrooted phylogenetic trees is FPT ⋮ Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ A fixed-parameter algorithm for minimum quartet inconsistency ⋮ Counting consistent phylogenetic trees is \#P-complete ⋮ A polynomial time algorithm for the minimum quartet inconsistency problem with \(O(n)\) quartet errors ⋮ Tree reconstruction from partial orders ⋮ Closure operations in phylogenetics ⋮ Reconstructing phylogenetic trees from multipartite quartet systems ⋮ Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors ⋮ A robust model for finding optimal evolutionary tree ⋮ Efficient approximation of convex recolorings ⋮ Trees, taxonomy, and strongly compatible multi-state characters ⋮ Inferring a level-1 phylogenetic network from a dense set of rooted triplets ⋮ On the Generalised Character Compatibility Problem for Non-branching Character Trees ⋮ Constructing big trees from short sequences ⋮ Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees ⋮ Reconstruction of rooted trees from subtrees ⋮ The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Optimizing tree and character compatibility across several phylogenetic trees ⋮ Minimum Average Distance Clique Trees ⋮ The size of the character state space affects the occurrence and detection of homoplasy: modelling the probability of incompatibility for unordered phylogenetic characters ⋮ A high quartet distance construction ⋮ On the quartet distance given partial information ⋮ New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem ⋮ A fast quartet tree heuristic for hierarchical clustering ⋮ Convex Characters, Algorithms, and Matchings ⋮ Phylogeny- and parsimony-based haplotype inference with constraints ⋮ Improved algorithms for maximum agreement and compatible supertrees ⋮ Graph triangulations and the compatibility of unrooted phylogenetic trees ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ Influence of tree topology restrictions on the complexity of haplotyping with missing data ⋮ THE REDUCTS OF THE HOMOGENEOUS BINARY BRANCHING C-RELATION ⋮ A simple characterization of the minimal obstruction sets for three-state perfect phylogenies ⋮ New fixed-parameter algorithms for the minimum quartet inconsistency problem ⋮ `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers ⋮ A few logs suffice to build (almost) all trees. II ⋮ A property tester for tree-likeness of quartet topologies ⋮ Testing consistency of quartet topologies: a parameterized approach ⋮ The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees ⋮ Learning Minimal Latent Directed Information Polytrees ⋮ Mathematical approaches to comparative linguistics ⋮ Recovering trees from well-separated multi-state characters. ⋮ Slim sets of binary trees ⋮ Identifying the rooted species tree from the distribution of unrooted gene trees under the coalescent ⋮ Groves of phylogenetic trees ⋮ Convex recolorings of strings and trees: Definitions, hardness results and algorithms ⋮ The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets ⋮ Reconstructing a phylogenetic level-1 network from quartets ⋮ On the weighted quartet consensus problem ⋮ Unique Perfect Phylogeny Is NP-Hard ⋮ Intervalizing k-colored graphs ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ Tree reconstruction from multi-state characters ⋮ Recovering a phylogenetic tree using pairwise closure operations ⋮ Approximability of clausal constraints ⋮ Peeling phylogenetic `oranges' ⋮ Building species trees from larger parts of phylogenomic databases ⋮ New results on optimizing rooted triplets consistency ⋮ Fixed-Parameter Algorithms for Finding Agreement Supertrees ⋮ Improved metaheuristics for the quartet method of hierarchical clustering ⋮ Integer linear programming as a tool for constructing trees from quartet data ⋮ Unnamed Item ⋮ Fast compatibility testing for rooted phylogenetic trees ⋮ Quarnet inference rules for level-1 networks ⋮ An exact algorithm for the minimum quartet tree cost problem ⋮ A colored graph approach to perfect phylogeny with persistent characters ⋮ Minimizing phylogenetic number to find good evolutionary trees ⋮ A note on convex characters, Fibonacci numbers and exponential-time algorithms ⋮ On the Maximum Quartet Distance between Phylogenetic Trees ⋮ Realization problems on reachability sequences ⋮ A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs ⋮ Reconstructing minimal rooted trees. ⋮ Combinatorial Scoring of Phylogenetic Networks ⋮ A Tractable Class of Binary VCSPs via M-Convex Intersection ⋮ Combining tree partitioning, precedence, and incomparability constraints ⋮ Consistency of the QNet algorithm for generating planar split networks from weighted quartets ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Determining the consistency of partial tree descriptions ⋮ Choosing the tree which actually best explains the data: another look at the bootstrap in phylogenetic reconstruction. ⋮ On the approximability of the Steiner tree problem in phylogeny ⋮ Inferring evolutionary trees with strong combinatorial evidence ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ A supertree method for rooted trees ⋮ Characterizing phylogenetically decisive taxon coverage ⋮ Identifying phylogenetic trees ⋮ Patching up \(X\)-trees ⋮ Matrix sandwich problems ⋮ Exponentially many supertrees ⋮ Minimum tree cost quartet puzzling
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstructing the shape of a tree from observed dissimilarity data
- Applications of antilexicographic order. I: An enumerative theory of trees
- Optimal algorithms for comparing trees with labeled leaves
- Invariants of phylogenies in a simple case with discrete states
- Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
- Tree enumeration modulo a consensus
- Consensus n-trees
- The Steiner problem in phylogeny is NP-complete
- Piecewise hierarchical clustering
- Convex tree realizations of partitions
- When are two qualitative taxonomic characters compatible?
- On the compatibility of binary qualitative taxonomic characters
- An algebraic analysis of cladistic characters
- A characterisation of rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On the Distribution of Lengths of Evolutionary Trees
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Tree structures for proximity data
- Computing the Minimum Fill-In is NP-Complete
- Efficient algorithms for inferring evolutionary trees
