Extension operations on sets of leaf-labelled trees
Trees with labelled leaves are useful models for representing evolutionary relationships, particularly in biology (where they are called phylogenetic trees). The wider availability of genetic sequence data, and the use of tree-building programs has led to a substantial increase in the size and number of phylogenetic trees. This trend has heightened the relevance of the generalized tree compatibility problem: determining whether a collection of phylogenetic trees on overlapping sets of taxa can be combined into one all-inclusive tree. Any ``divide and conquer technique for large classifications encounters this problem, as would any attempt to incorporate the many existing phylogenies into new phylogenetic trees. Tree compatibility can be efficiently determined when all the input trees are either all rooted or have a leaf in common. If the trees have the same leaf sets then compatibility can be determined in linear time. However, the general problem for unrooted trees is NP-complete. A further problem in combining phylogenetic trees is that any tree constructed might be only one among a multitude of possible trees, each of which is well supported by the data. In practice there are often thousands of suitable trees consistent with any given data set. This reflects the exponentially large number of possible phylogenetic trees. Our approach is to break the initial collection of trees into an equivalent set of binary trees, each with three leaves (rooted triples) or four leaves (quartets). In this way, many of the original problems involving phylogenetic trees can be converted into equivalent problems involving these sets. In the remainder of this section we define phylogenetic trees and compatibility, giving a brief survey of related concepts in the literature. We characterize compatibility in terms of quartets and rooted triples and discuss when a collection of subtrees defines a unique tree. Section 2 introduces compatibility rules for quartet sets and proves a number of related properties. Section 3 examines sets of rooted triples and presents a new graphical characterization of consistency and closure. In Section 4 we use this graphical representation to prove that there are rules of any order that cannot be derived from rules of lesser order. The result is proved first for rooted triples and then extended to quartets.
- Quartet compatibility and the quartet graph
- Phylogenetic graph models beyond trees
- On the approximability of the maximum agreement subtree and maximum compatible tree problems
- Characterizing phylogenetically decisive taxon coverage
- Convex tree realizations of partitions
- The complexity of reconstructing trees from qualitative characters and subtrees
- A supertree method for rooted trees
- Minimum triplet covers of binary phylogenetic \(X\)-trees
- Phylogenetic flexibility via Hall-type inequalities and submodularity
- The matroid structure of representative triple sets and triple-closure computation
- Inferring phylogenetic trees from the knowledge of rare evolutionary events
- Quarnet inference rules for level-1 networks
- Reconstructing gene trees from Fitch's xenology relation
- Explosions and hot spots in supertree methods
- Reconstructing minimal rooted trees.
- A few logs suffice to build (almost) all trees. II
- The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
- Tree representations of non-symmetric group-valued proximities
- Corrigendum to: ``Best match graphs
- On the comparison of incompatibility of split systems across different numbers of taxa
- Indirect identification of horizontal gene transfer
- Best match graphs with binary trees
- Compatibility of partitions with trees, hierarchies, and split systems
- Reconstructing phylogenetic trees from multipartite quartet systems
- Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
- Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
- Closure operations in phylogenetics
- Best match graphs
- Maximum agreement and compatible supertrees
- Recovering a phylogenetic tree using pairwise closure operations
- Identifying phylogenetic trees
- Complete characterization of incorrect orthology assignments in best match graphs
- Quasi-best match graphs
- A navigation system for tree space
- The reducts of the homogeneous binary branching C-relation
- scientific article; zbMATH DE number 4130396 (Why is no real title available?)
- Some axiomatic limitations for consensus and supertree functions on hierarchies
- scientific article; zbMATH DE number 5999306 (Why is no real title available?)
- An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
- Mathematical aspects of phylogenetic groves
- \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time
- Kernel and fast algorithm for dense triplet inconsistency
- Optimizing tree and character compatibility across several phylogenetic trees
- Matchings and phylogenetic trees
- `Bureaucratic' set systems, and their role in phylogenetics
- scientific article; zbMATH DE number 1746444 (Why is no real title available?)
- The complexity of phylogeny constraint satisfaction
- A characterization of dissimilarity families of trees
- Deciding the closure of inconsistent rooted triples is NP-complete
- Reconstructing phylogenetic tree from multipartite quartet system
- Treelike quintet systems
- Representations of partial leaf sets in phylogenetic tree space
- The complexity of phylogeny constraint satisfaction problems
- Fast compatibility testing for rooted phylogenetic trees
- Building species trees from larger parts of phylogenomic databases
- Representing and extending ensembles of parsimonious evolutionary histories with a directed acyclic graph
- Graph triangulations and the compatibility of unrooted phylogenetic trees
- Slim sets of binary trees
- Groves of phylogenetic trees
- Transformations to simplify phylogenetic networks
- Inferring DAGs and phylogenetic networks from least common ancestors
- Compatibility of unrooted phylogenetic trees is FPT
- Encoding phylogenetic trees in terms of weighted quartets
This page was built for publication: Extension operations on sets of leaf-labelled trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1914784)
