PhySIC: A Veto Supertree Method with Desirable Properties. 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 non-contradiction 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, whereas 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(kn3 + n4) 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 require consolidation. Lastly, we illustrate the behaviour of PhySIC on primate data sets of various sizes, and propose a supertree covering 95% of all primate extant genera. The PhySIC algorithm is available at http://atgc.lirmm.fr/cgi-bin/PhySIC.
Keywords for this software
References in zbMATH (referenced in 8 articles )
Showing results 1 to 8 of 8.
- Warnow, Tandy (ed.): Bioinformatics and phylogenetics. Seminal contributions of Bernard Moret (2019)
- Seemann, Carsten R.; Hellmuth, Marc: The matroid structure of representative triple sets and triple-closure computation (2018)
- van Iersel, Leo; Moulton, Vincent: Trinets encode tree-child and level-2 phylogenetic networks (2014)
- Brinkmeyer, Malte; Griebel, Thasso; Böcker, Sebastian: \textscFlipCutsupertrees: towards matrix representation accuracy in polynomial time (2013)
- Bansal, Mukul S.; Dong, Jianrong; Fernández-Baca, David: Comparing and aggregating partially resolved trees (2011)
- Brinkmeyer, Malte; Griebel, Thasso; Böcker, Sebastian: Polynomial supertree methods revisited (2011) ioport
- Scornavacca, C.; Berry, V.; Ranwez, V.: Building species trees from larger parts of phylogenomic databases (2011)
- Scornavacca, Celine; Berry, Vincent; Ranwez, Vincent: From gene trees to species trees through a supertree approach (2009)