In [13], the authors introduced the Generalised Character Compatibility Problem as a generalisation of the Perfect Phylogeny Problem for a set of species. This generalised problem takes into account the fact that while a species may not be expressing a certain trait, i.e., having teeth, its DNA may contain data for this trait in a non-functional region. The authors showed that the Generalised Character Compatibility Problem is NP-complete for an instance of the problem involving five states, where the characters' state transition trees are branching. They also presented a class of instances of the problem that is polynomial-time solvable. The authors posed an open problem about the complexity of this problem when no branching is allowed in the character trees. They answered this question in [2], where they showed that for an instance in which each character tree is 0→1→2 (no branching), and only the states 1,0,2,0,1,2 are allowed, is NP-complete. This, however, does not provide an answer to the exact question posed in [3], which allows only one type of generalised state: 0,2, called here the Benham-Kannan-Warnow (BKW) Case. In this paper, we study the complexity of various versions of this problem with non-branching character trees, depending on the set of states allowed, and depending on the restriction on the phylogeny tree: any tree, path or single-branch tree. In particular, we show that if the phylogeny tree is required to have only one branch: (a) the problem still remains NP-complete (for instance with states 1,0,2,0,1,2), and (b) the problem is polynomial-time solvable in the BKW Case (with states 0,1,2,0,2). We show the second result by unveiling a surprising connection to the Consecutive-Ones Property (C1P) Problem, used for instance, in DNA physical mapping, interval graph recognition and data retrieval. © 2009 Springer Berlin Heidelberg

Maňuch, J., Patterson, M., Gupta, A. (2009). On the generalised character compatibility problem for non-branching character trees. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.268-276) [10.1007/978-3-642-02882-3_27].

On the generalised character compatibility problem for non-branching character trees

Patterson, Murray;
2009

Abstract

In [13], the authors introduced the Generalised Character Compatibility Problem as a generalisation of the Perfect Phylogeny Problem for a set of species. This generalised problem takes into account the fact that while a species may not be expressing a certain trait, i.e., having teeth, its DNA may contain data for this trait in a non-functional region. The authors showed that the Generalised Character Compatibility Problem is NP-complete for an instance of the problem involving five states, where the characters' state transition trees are branching. They also presented a class of instances of the problem that is polynomial-time solvable. The authors posed an open problem about the complexity of this problem when no branching is allowed in the character trees. They answered this question in [2], where they showed that for an instance in which each character tree is 0→1→2 (no branching), and only the states 1,0,2,0,1,2 are allowed, is NP-complete. This, however, does not provide an answer to the exact question posed in [3], which allows only one type of generalised state: 0,2, called here the Benham-Kannan-Warnow (BKW) Case. In this paper, we study the complexity of various versions of this problem with non-branching character trees, depending on the set of states allowed, and depending on the restriction on the phylogeny tree: any tree, path or single-branch tree. In particular, we show that if the phylogeny tree is required to have only one branch: (a) the problem still remains NP-complete (for instance with states 1,0,2,0,1,2), and (b) the problem is polynomial-time solvable in the BKW Case (with states 0,1,2,0,2). We show the second result by unveiling a surprising connection to the Consecutive-Ones Property (C1P) Problem, used for instance, in DNA physical mapping, interval graph recognition and data retrieval. © 2009 Springer Berlin Heidelberg
paper
Theoretical Computer Science; Computer Science (all)
English
Annual International Conference on Computing and Combinatorics, COCOON 2009 13-15 July
2009
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-364202881-6
2009
5609
268
276
reserved
Maňuch, J., Patterson, M., Gupta, A. (2009). On the generalised character compatibility problem for non-branching character trees. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.268-276) [10.1007/978-3-642-02882-3_27].
File in questo prodotto:
File Dimensione Formato  
Maňuch-2009-Cocoon-VoR.pdf

Solo gestori archivio

Descrizione: Conference Paper
Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Tutti i diritti riservati
Dimensione 170.58 kB
Formato Adobe PDF
170.58 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/217385
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
Social impact