A Novel Insight into the Perfect Phylogeny Problem

摘要

One of the classical problem in computational biology is the character compatibility problem or perfect phylogeny problem. A standard formulation of this problem in terms of two closely related questions is the following. Given a data set consisting of a finite set X and a set $$ {user1{mathcal{R}}} $$ of partitions induced on X by a set of characters. Is $$ {user1{mathcal{R}}} $$ compatible, that is, does there exist an evolutionary tree that represents (in a well-defined sense) the data? If this is the case, is this tree unique? A fundamental result in phylogenetics states that the answer to the former of the two questions is yes precisely if the partition intersection graph $$ I_{{user1{mathcal{R}}}} $$ associated to $$ {user1{mathcal{R}}} $$ can be made chordal by obeying a certain rule.