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 of partitions induced on X by a set of characters. Is 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 associated to can be made chordal by obeying a certain rule. The main insight from this paper is that the relation graph associated to a set of partitions may provide a key for deciding whether such a chordalization of exists. To prove our results, we introduce an extension of the concept of the partition intersection graph associated to using . Received August 27, 2004