PhySIC: A Veto Supertree Method with Desirable Properties

Abstract : This paper focuses on veto supertree methods, i.e., methods that aim at producing a conservative synthesis of the relationships agreed upon by all source trees. We propose desirable properties that a supertree should satisfy in this framework, namely the noncontradiction property (PC) and the induction property (PI). The former requires that the supertree does not contain relationships that contradict one or a combination of the source topologies, while the latter requires that all topological information contained in the supertree is present in a source tree or collectively induced by several source trees. We provide simple examples to illustrate their relevance and that allow a comparison with previously advocated properties. We show that these properties can be checked in polynomial time for any given rooted supertree. Moreover, we introduce the PhySIC method (phylogenetic signal with induction and non-contradiction). For k input trees spanning a set of n taxa, this method produces a supertree that satisfies the above-mentioned properties in O(kn^3 + n^4) polynomial computing time. The polytomies of the produced supertree are also tagged by labels indicating areas of conflict as well as those with insufficient overlap. As a whole, PhySIC enables the user to quickly summarize consensual information of a set of trees and localize groups of taxa for which the data requires consolidation. Lastly, we illustrate the behaviour of PhySIC on primate datasets of various sizes, and propose a supertree covering 95% of all primate extant genera. The PhySIC algorithm is available at
Liste complète des métadonnées
Contributeur : Vincent Berry <>
Soumis le : jeudi 13 décembre 2007 - 20:22:18
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : lundi 12 avril 2010 - 06:21:08


  • HAL Id : lirmm-00194235, version 1



Vincent Ranwez, Vincent Berry, Alexis Criscuolo, Pierre-Henri Fabre, Sylvain Guillemot, et al.. PhySIC: A Veto Supertree Method with Desirable Properties. Systematic Biology, Oxford University Press (OUP), 2007, 56 (5), pp.293-304. 〈〉. 〈lirmm-00194235〉



Consultations de la notice


Téléchargements de fichiers