Merging partially labelled trees: hardness and a declarative programming solution

Anthony Labarre 1, * Sicco Verwer 2
* Auteur correspondant
1 AlgoB
LIGM - Laboratoire d'Informatique Gaspard-Monge
Abstract : Intraspecific studies often make use of haplotype networks instead of gene genealogies to represent the evolution of a set of genes. Cassens et al. proposed one such network reconstruction method, based on the global maximum parsimony principle, which was later recast by the first author of the present work as the problem of finding a minimum common supergraph of a set of t partially labelled trees. Although algorithms were proposed for solving the problem on two graphs, the complexity of the general problem remains unknown. In this paper, we show that the corresponding decision problem is NP-complete for t = 3. We then propose a declarative programming approach to solving the problem to optimality in practice, as well as a heuristic approach, both based on the IDP system, and assess the performance of both methods on randomly generated data.
Type de document :
Article dans une revue
IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2014, 11 (2), pp.389-397. 〈10.1109/TCBB.2014.2307200〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-00855669
Contributeur : Anthony Labarre <>
Soumis le : lundi 7 juillet 2014 - 18:40:26
Dernière modification le : mercredi 15 avril 2015 - 16:11:30
Document(s) archivé(s) le : mardi 7 octobre 2014 - 10:36:36

Fichier

ump-is-hard-shortened.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Anthony Labarre, Sicco Verwer. Merging partially labelled trees: hardness and a declarative programming solution. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2014, 11 (2), pp.389-397. 〈10.1109/TCBB.2014.2307200〉. 〈hal-00855669〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

118