Extension operations on sets of leaf-labelled trees
type: Item
instance of: scholarly article
title: Extension operations on sets of leaf-labelled trees
zbMATH Open document ID: 0863.92012
published in: Advances in Applied Mathematics
publication date: 1997-06-12T00:00:00Z
review text: 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 numbe…
Mathematics Subject Classification ID: 92D15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 92B05
zbMATH DE Number: 885458
zbMATH Keywords: quartets
zbMATH Keywords: rooted triples
zbMATH Keywords: labelled leaves
zbMATH Keywords: phylogenetic trees
zbMATH Keywords: generalized tree compatibility problem
zbMATH Keywords: overlapping sets of taxa
zbMATH Keywords: graphical characterization of consistency and closure
author: David Bryant
author: Mike Steel
MaRDI profile type: Publication
full work available at URL: aama.1995.1020
OpenAlex ID: W2009661773
DOI: 10.1006/AAMA.1995.1020
description: scientific article; zbMATH DE number 885458