Trees, Taxonomy, and Strongly Compatible Multi-state Characters

✍ Scribed by Andreas Dress; Vincent Moulton; Michael Steel

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 350 KB
• Volume: 19
• Category: Article
• ISSN: 0196-8858
• DOI: 10.1006/aama.1996.0503

✦ Synopsis

Given a family of binary characters defined on a set X, a problem arising in biological and linguistic classification is to decide whether there is a tree structure on X which is ''compatible'' with this family. A fundamental result from hierarchical clustering theory states that there exists a tree structure on X for such a family if and only if any two of the characters are compatible. In this paper, we prove a generalization of this result. Namely, we show that given a family of multi-state characters on X which we denote by , there exists a tree structure on X, called Ž . an X, -tree, which is ''compatible'' with if and only if any two of the characters are strongly compatible. To prove this result, we introduce the concept of block systems, set theoretical structures which arise naturally from, amongst other things, block graphs, and the related concepts of block inter¨al systems and ⌬systems.