Quartet compatibility and the quartet graph (2005)
Type of ContentDiscussion / Working Papers
PublisherUniversity of Canterbury. Dept. of Mathematics and Statistics
- Engineering: Reports 
A collection P of leaf-labelled trees is compatible if there exists a single leaf-labelled tree that displays each of the trees in P. Despite its difficulty, determining the compatibility of P is a fundamental task in evolutionary biology. Attractive characterizations in terms of chordal graphs have been previously given for this problem as well as for the problems of (i) determining if there is a unique tree that displays each of the trees in P, that is 'P is definitive and (ii) determining if there is a tree that displays P and has the property that every other tree that displays P is a refinement of it, that is 'P identifies a leaf-labelled tree. In this paper, we describe new characterizations of each of these problems in terms of edge colourings. Furthermore, for an arbitrary leaf-labelled tree 'T, we also determine the minimum number of 'quartets' required to identify 'T, thus correcting a previously published result.
KeywordsPhylogenetic tree; compatibility; restricted chordal completion; identifies
ANZSRC Fields of Research49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics
31 - Biological sciences::3104 - Evolutionary biology::310410 - Phylogeny and comparative analysis
RightsCopyright Stefan Grünewald
Showing items related by title, author, creator and subject.
Francis A; Semple C; Steel M (2017)Phylogenetic networks are a type of directed acyclic graph that represent how a set X of present-day species are descended from a common ancestor by processes of speciation and reticulate evolution. In the absence of ...
Bordewich, M.; Semple, C.; Talbot, J. (University of Canterbury, 2003)Reconstructing phylogenetic trees is a fundamental task in evolutionary biology. Various algorithms exist for this purpose, many of which come under the heading of 'supertree methods'. These methods amalgamate a collection ...
Van Iersel, L.; Semple, C.; Steel, M. (University of Canterbury. Dept. of Mathematics and Statistics, 2009)The complex pattern of presence and absence of many genes across different species provides tantalising clues as to how genes evolved through the processes of gene genesis, gene loss and lateral gene transfer (LGT). The ...