Quartet compatibility and the quartet graph

Stefan Grünewald ; Peter J. Humphries ; Charles Semple

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

A collection ${\cal P}$ of phylogenetic trees is compatible if there exists a single phylogenetic tree that displays each of the trees in ${\cal P}$. Despite its computational difficulty, determining the compatibility of ${\cal P}$ is a fundamental task in evolutionary biology. Characterizations in terms of chordal graphs have been previously given for this problem as well as for the closely-related problems of (i) determining if ${\cal P}$ is definitive and (ii) determining if ${\cal P}$ identifies a phylogenetic tree. In this paper, we describe new characterizations of each of these problems in terms of edge colourings. Furthermore, making use of the tools that underlie these new characterizations, we also determine the minimum number of quartets required to identify an arbitrary phylogenetic tree, thus correcting a previously published result.

Détail

DOI : 10.37236/827

Classification : 05C62, 05C05, 92B10
Mots-clés : phylogenetic trees, evolutionary biology, chordal graphs, edge colourings, quartets, quartet graph