Directed Perfect Phylogeny (Binary Characters)

Keywords and Synonyms

Directed binary character compatibility          

Problem Definition

Let ${ S = \{s_1,s_2,\dots,s_n\} }$ be a set of elements called objects, and let ${ C = \{c_1,c_2,\dots,c_m\} }$ be a set of functions from S to ${ \{0,1\} }$ called characters. For each object ${ s_i \in S }$ and character ${ c_j \in C }$, it is said that s _i has c _j if ${ c_j(s_i) = 1 }$ or that s _i does not have c _j if ${ c_j(s_i) = 0 }$, respectively (in this sense, characters are binary). Then the set S and its relation to C can be naturally represented by a matrix M of size ${ (n \times m) }$ satisfying ${ M[i,j] = c_j(s_i) }$ for every ${ i \in \{1,2,\dots,n\} }$ and ${ j \in \{1,2,\dots,m\} }$. Such a matrix M is called a binary character state matrix.

Next, for each $s_i \in S$, define the set $C_{s_i} = \{c_j \in C \colon s_i {\text{\ has\ }} c_j\}$. A phylogeny for S is a tree whose leaves are bijectively labeled by S, and a directed perfect...