Identifying phylogenetic trees

Bordewich, M.; Huber, K.; Semple, C.

Abstract

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection C of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays C have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when C identifies an X-tree, and the second describes when a compatible subset of C is of maximum size.

Citation

Bordewich, M., Huber, K., & Semple, C. (2005). Identifying phylogenetic trees. Discrete Mathematics, 300(1-3), 30-43. https://doi.org/10.1016/j.disc.2005.06.015

• Journal Article Type: Article
• Publication Date: 2005-09
• Journal: Discrete mathematics.
• Print ISSN: 0012-365X
• Publisher: Elsevier
• Volume: 300
• Issue: 1-3
• Pages: 30-43
• DOI: https://doi.org/10.1016/j.disc.2005.06.015
• Keywords: Phylogenetic tree; Identifying; Restricted chordal completion