Representing a set of reconciliations in a compact way

Abstract : Comparative genomic studies are often conducted by reconciliation analyses comparing gene and species trees. One of the issues with reconciliation approaches is that an exponential number of optimal scenarios is possible. The resulting complexity is masked by the fact that a majority of reconciliation software pick up a random optimal solution that is returned to the end-user. However, the alternative solutions should not be ignored since they tell different stories that parsimony considers as viable as the output solution. In this paper, we describe a polynomial space and time algorithm to build a minimum reconciliation graph -- a graph that summarizes the set of all most parsimonious reconciliations. Amongst numerous applications, it is shown how this graph allows counting the number of non-equivalent most parsimonious reconciliations.
Type de document :
Article dans une revue
Journal of Bioinformatics and Computational Biology, World Scientific Publishing, 2013, 11 (2), pp.1250025. 〈http://www.worldscientific.com/doi/abs/10.1142/S0219720012500254〉. 〈10.1142/S0219720012500254〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00818801
Contributeur : Vincent Berry <>
Soumis le : mercredi 22 mai 2013 - 14:20:05
Dernière modification le : jeudi 26 octobre 2017 - 13:44:08
Document(s) archivé(s) le : mardi 4 avril 2017 - 01:38:29

Fichier

article_graphDTL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Celine Scornavacca, Wojciech Paprotny, Vincent Berry, Vincent Ranwez. Representing a set of reconciliations in a compact way. Journal of Bioinformatics and Computational Biology, World Scientific Publishing, 2013, 11 (2), pp.1250025. 〈http://www.worldscientific.com/doi/abs/10.1142/S0219720012500254〉. 〈10.1142/S0219720012500254〉. 〈lirmm-00818801〉

Partager

Métriques

Consultations de la notice

409

Téléchargements de fichiers

424