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 http://www.atgc-montpellier.fr/physic/
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00194235
Contributor : Vincent Berry <>
Submitted on : Thursday, December 13, 2007 - 8:22:18 PM
Last modification on : Thursday, October 24, 2019 - 9:54:26 AM
Long-term archiving on : Monday, April 12, 2010 - 6:21:08 AM

Identifiers

  • HAL Id : lirmm-00194235, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

374

Files downloads

413