On a conjecture of compatibility of multi-states characters

Details On a conjecture of compatibility of multi-states characters On a conjecture of compatibility of multi-states characters

2011-05-05

arxiv.org/abs/1105.1109v1

Computer Science

Data Structures and Algorithms

Scientific paper

Perfect phylogeny consisting of determining the compatibility of a set of characters is known to be NP-complete. We propose in this article a conjecture on the necessary and sufficient conditions of compatibility: Given a set $\mathcal{C}$ of $r$-states full characters, there exists a function $f(r)$ such that $\mathcal{C}$ is compatible iff every set of $f(r)$ characters of $\mathcal{C}$ is compatible. Some previous work showed that $f(2)=2$, $f(3)=3$ and $f(r) \ge r-1$. Gusfield et al. 09 conjectured that $f(r) = r$ for any $r \ge 2$. In this paper, we present an example showing that $f(4) \ge 5$ and then a closure operation for chordal sandwich graphs. The later problem is a common approach of perfect phylogeny. This operation can be the first step to simplify the problem before solving some particular cases $f(4), f(5), ... $, and determining the function $f(r)$.

Affiliated with

Also associated with

No associations

Rating

On a conjecture of compatibility of multi-states 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 On a conjecture of compatibility of multi-states characters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a conjecture of compatibility of multi-states characters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-691034