05946450

a

05946450 Habib, Michel To, Thu-Hien On a conjecture about compatibility of multi-states characters. Przytycka, Teresa M. (ed.) et al., Algorithms in bioinformatics. 11th international workshop, WABI 2011, Saarbr\"ucken, Germany, September 5--7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23037-0/pbk). Lecture Notes in Computer Science 6833. Lecture Notes in Bioinformatics, 116-127 (2011). 2011 Berlin: Springer EN perfect phylogeny characters compatibility chordal sandwich graph vertex-coloured graph triangulation

doi:10.1007/978-3-642-23038-7_11

Summary: Perfect phylogeny consisting of determining the compatibility of a set of characters is known to be NP-complete [4,28]. 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. According to [7,9,8,25,11,23], $f(2) = 2$, $f(3) = 3$ and $f(r) \geq r$. [23] conjectured that $f(r) = r$ for any $r \geq 2$. In this paper, we present an example showing that $f(4) \geq 5$. Therefore it could be the case that for $r \geq 4$ characters the problem behavior drastically changes. In a second part, we propose a closure operation for chordal sandwich graphs. The later problem is a common approach of perfect phylogeny.