The complexity of reconstructing trees from qualitative characters and subtrees

DOI10.1007/BF02618470zbMATH Open0766.92002MaRDI QIDQ1203103FDOQ1203103

Authors: Mike Steel 

Publication date: 4 February 1993

Published in: Journal of Classification (Search for Journal in Brave)

Recommendations

• On the complexity of constructing evolutionary trees
• scientific article; zbMATH DE number 1088267
• The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
• Tree reconstruction from partial orders
• Extension operations on sets of leaf-labelled trees

zbMATH Keywords

computational complexityclustersalgorithmNP-completepolynomial timecompatibilityrooted treesunrooted treesstrict consensus treeoverlapping sets of labelsparent treespartial binary charactersqualitative charactersresolved quartetsrooted subtreestree-like classifications

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Taxonomy, cladistics, statistics in mathematical biology (92B10)

Cites Work

• Reconstructing the shape of a tree from observed dissimilarity data
• Tree structures for proximity data
• Title not available (Why is that?)
• Consensus n-trees
• The Steiner problem in phylogeny is NP-complete
• Graph theory with applications
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Applications of antilexicographic order. I: An enumerative theory of trees
• Title not available (Why is that?)
• Efficient algorithms for inferring evolutionary trees
• Computing the Minimum Fill-In is NP-Complete
• 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
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• A characterisation of rigid circuit graphs
• Convex tree realizations of partitions
• On the Distribution of Lengths of Evolutionary Trees
• When are two qualitative taxonomic characters compatible?
• On the compatibility of binary qualitative taxonomic characters
• An algebraic analysis of cladistic characters
• Tree enumeration modulo a consensus
• Piecewise hierarchical clustering
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Kernel and fast algorithm for dense triplet inconsistency
• Optimizing tree and character compatibility across several phylogenetic trees
• Identifying phylogenetic trees
• Characterizing phylogenetically decisive taxon coverage
• Minimum tree cost quartet puzzling
• New results on optimizing rooted triplets consistency
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Approximability of clausal constraints
• A supertree method for rooted trees
• Algorithms and complexity of sandwich problems in graphs (extended abstract)
• Phylogeny- and parsimony-based haplotype inference with constraints
• Peeling phylogenetic `oranges'
• A polynomial time algorithm for the minimum quartet inconsistency problem with \(O(n)\) quartet errors
• On the approximability of the Steiner tree problem in phylogeny
• Building species trees from larger parts of phylogenomic databases
• On the maximum quartet distance between phylogenetic trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Matrix sandwich problems
• Influence of tree topology restrictions on the complexity of haplotyping with missing data
• On the Generalised Character Compatibility Problem for Non-branching Character Trees
• Patching up \(X\)-trees
• Fast compatibility testing for rooted phylogenetic trees
• Inferring evolutionary trees with strong combinatorial evidence
• A few logs suffice to build (almost) all trees. II
• New fixed-parameter algorithms for the minimum quartet inconsistency problem
• Reconstructing minimal rooted trees.
• A colored graph approach to perfect phylogeny with persistent characters
• A note on convex characters, Fibonacci numbers and exponential-time algorithms
• Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors
• Minimizing phylogenetic number to find good evolutionary trees
• A fixed-parameter algorithm for minimum quartet inconsistency
• A robust model for finding optimal evolutionary tree
• A simple characterization of the minimal obstruction sets for three-state perfect phylogenies
• Reconstruction of rooted trees from subtrees
• Teasing Apart Two Trees
• The computational complexity of inferring rooted phylogenies by parsimony
• Tree reconstruction from multi-state characters
• Mathematical approaches to comparative linguistics
• Compatibility of unrooted phylogenetic trees is FPT
• On the approximability of the Steiner tree problem in phylogeny
• Determining the consistency of partial tree descriptions
• Recovering a phylogenetic tree using pairwise closure operations
• A fast quartet tree heuristic for hierarchical clustering
• Graph triangulations and the compatibility of unrooted phylogenetic trees
• Efficient approximation of convex recolorings
• Complexity of splits reconstruction for low-degree trees
• Closure operations in phylogenetics
• Improved algorithms for maximum agreement and compatible supertrees
• Combining tree partitioning, precedence, and incomparability constraints
• Reconstructing phylogenetic trees from multipartite quartet systems
• Reconstructing a phylogenetic level-1 network from quartets
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• A property tester for tree-likeness of quartet topologies
• The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
• Consistency of the QNet algorithm for generating planar split networks from weighted quartets
• Slim sets of binary trees
• Trees, taxonomy, and strongly compatible multi-state characters
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• On compatibility and incompatibility of collections of unrooted phylogenetic trees
• Identifying the rooted species tree from the distribution of unrooted gene trees under the coalescent
• Groves of phylogenetic trees
• Title not available (Why is that?)
• Fixed-Parameter Algorithms for Finding Agreement Supertrees
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers
• Constructing big trees from short sequences
• Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
• Integer linear programming as a tool for constructing trees from quartet data
• Testing consistency of quartet topologies: a parameterized approach
• Exponentially many supertrees
• The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
• Convex Characters, Algorithms, and Matchings
• The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
• On the weighted quartet consensus problem
• The matroid structure of representative triple sets and triple-closure computation
• Quarnet inference rules for level-1 networks
• Counting consistent phylogenetic trees is \#P-complete
• Tree reconstruction from partial orders
• The reducts of the homogeneous binary branching \(C\)-relation
• Variational supertrees for Bayesian phylogenetics
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
• Combinatorial scoring of phylogenetic networks
• Improved metaheuristics for the quartet method of hierarchical clustering
• Solving infinite-domain CSPs using the patchwork property
• New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem
• A tractable class of binary VCSPs via M-convex intersection
• An exact algorithm for the minimum quartet tree cost problem
• Minimum average distance clique trees
• Unique perfect phylogeny is NP-hard
• Learning minimal latent directed information polytrees
• On the quartet distance given partial information
• Title not available (Why is that?)
• Realization problems on reachability sequences
• Consistency and inconsistency of consensus methods for inferring species trees from gene trees in the presence of ancestral population structure
• A linear time approximation scheme for maximum quartet consistency on sparse sampled inputs
• Phylogenetic trees defined by at most three characters
• Choosing the tree which actually best explains the data: another look at the bootstrap in phylogenetic reconstruction.
• The size of the character state space affects the occurrence and detection of homoplasy: modelling the probability of incompatibility for unordered phylogenetic characters
• Recovering trees from well-separated multi-state characters.
• A high quartet distance construction
• Intervalizing \(k\)-colored graphs

This page was built for publication: The complexity of reconstructing trees from qualitative characters and subtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1203103)