Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters

Details Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters

2009-05-09

arxiv.org/abs/0905.1417v2

Mathematics

Combinatorics

Scientific paper

We study the perfect phylogeny problem and establish a generalization of the four gamete condition (also called the Splits Equivalence Theorem) for sequences over three state characters. Our main result is that a set of input sequences over three state characters allows a perfect phylogeny if and only if every subset of three characters allows a perfect phylogeny. In establishing these results, we prove fundamental structural features of the perfect phylogeny problem on three state characters and completely characterize the minimal obstruction sets that must occur in three state input sequences that do not have a perfect phylogeny. We further give a proof for a stated lower bound involved in the conjectured generalization of our main result to any number of states. The techniques are based on the chordal graph view of perfect phylogeny. Until this work, the notion of a conflict, or incompatibility, graph has been defined for two state characters only. Our generalization of the four gamete condition allows us to generalize the notion of incompatibility to three state characters. The resulting incompatibility structure is a hypergraph, which can be used to solve algorithmic and theoretical problems.

Affiliated with

Also associated with

No associations

Rating

Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689222