{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:39:16Z","timestamp":1757543956635},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Supertree methods combine phylogenies with overlapping sets of taxa into a larger one. Topological conflicts frequently arise among source trees for methodological or biological reasons, such as long branch attraction, lateral gene transfers, gene duplication\/loss or deep gene coalescence. When topological conflicts occur among source trees, <jats:italic>liberal<\/jats:italic> methods infer supertrees containing the most frequent alternative, while <jats:italic>veto<\/jats:italic> methods infer supertrees not contradicting any source tree, <jats:italic>i.e<\/jats:italic>. discard all conflicting resolutions. When the source trees host a significant number of topological conflicts or have a small taxon overlap, supertree methods of both kinds can propose poorly resolved, hence uninformative, supertrees.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>To overcome this problem, we propose to infer non-plenary supertrees, <jats:italic>i.e<\/jats:italic>. supertrees that do not necessarily contain all the taxa present in the source trees, discarding those whose position greatly differs among source trees or for which insufficient information is provided. We detail a variant of the <jats:italic>PhySIC<\/jats:italic> veto method called <jats:italic>PhySIC_IST<\/jats:italic> that can infer non-plenary supertrees. <jats:italic>PhySIC_IST<\/jats:italic> aims at inferring supertrees that satisfy the same appealing theoretical properties as with <jats:italic>PhySIC<\/jats:italic>, while being as informative as possible under this constraint. The informativeness of a supertree is estimated using a variation of the CIC (Cladistic Information Content) criterion, that takes into account both the presence of multifurcations and the absence of some taxa. Additionally, we propose a statistical preprocessing step called STC (Source Trees Correction) to correct the source trees prior to the supertree inference. STC is a liberal step that removes the parts of each source tree that significantly conflict with other source trees. Combining STC with a veto method allows an explicit trade-off between veto and liberal approaches, tuned by a single parameter.<\/jats:p>\n            <jats:p>Performing large-scale simulations, we observe that STC+<jats:italic>PhySIC_IST<\/jats:italic> infers much more informative supertrees than <jats:italic>PhySIC<\/jats:italic>, while preserving low type I error compared to the well-known MRP method. Two biological case studies on animals confirm that the STC preprocess successfully detects anomalies in the source trees while STC+<jats:italic>PhySIC_IST<\/jats:italic> provides well-resolved supertrees agreeing with current knowledge in systematics.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The paper introduces and tests two new methodologies, <jats:italic>PhySIC_IST<\/jats:italic> and STC, that demonstrate the interest in inferring non-plenary supertrees as well as preprocessing the source trees. An implementation of the methods is available at: <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/www.atgc-montpellier.fr\/physic_ist\/\" ext-link-type=\"uri\">http:\/\/www.atgc-montpellier.fr\/physic_ist\/<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-9-413","type":"journal-article","created":{"date-parts":[[2008,10,4]],"date-time":"2008-10-04T18:13:18Z","timestamp":1223143998000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":39,"title":["PhySIC_IST: cleaning source trees to infer more informative supertrees"],"prefix":"10.1186","volume":"9","author":[{"given":"Celine","family":"Scornavacca","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Berry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Lefort","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanuel JP","family":"Douzery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Ranwez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,10,4]]},"reference":[{"key":"2398_CR1","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1201\/9781420009538.ch6","volume-title":"Reconstructing the Tree of Life: Taxonomy and Systematics of Species Rich Taxa","author":"ORP Bininda-Edmonds","year":"2006","unstructured":"Bininda-Edmonds ORP, Stamatakis A: Taxon sampling versus computational complexity and their impact on obtaining the Tree of Life. In Reconstructing the Tree of Life: Taxonomy and Systematics of Species Rich Taxa. Volume 72. Edited by: Hodkinson T, Parnell J. New York: Systematics Association Special Series, CRC Press; 2006:77\u201395."},{"key":"2398_CR2","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1016\/S0076-6879(05)95038-6","volume":"395","author":"ORP Bininda-Edmonds","year":"2005","unstructured":"Bininda-Edmonds ORP: Supertree construction in the genomic age. Methods Enzymol 2005, 395: 745\u201357.","journal-title":"Methods Enzymol"},{"key":"2398_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-1-4020-2330-9_2","volume-title":"Phylogenetic supertrees: combining information to reveal the Tree of Life","author":"BR Baum","year":"2004","unstructured":"Baum BR, Ragan MA: The MRP method. In Phylogenetic supertrees: combining information to reveal the Tree of Life Edited by: Bininda-Emonds O, Kluwer. 2004, 17\u201334."},{"key":"2398_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0166-218X(00)00202-X","volume":"105","author":"C Semple","year":"2000","unstructured":"Semple C, Steel M: A supertree method for rooted trees. Discrete Appl Math 2000, 105: 147\u2013158.","journal-title":"Discrete Appl Math"},{"key":"2398_CR5","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/3-540-45784-4_41","volume-title":"Proceedings of the 2nd International Workshop on Algorithms in Bioinformatics (WABI'02)","author":"RDM Page","year":"2002","unstructured":"Page RDM: Modified mincut supertrees. In Proceedings of the 2nd International Workshop on Algorithms in Bioinformatics (WABI'02) Edited by: Guig\u00f3 R, Gusfield D. 2002, 537\u2013552."},{"issue":"4","key":"2398_CR6","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1109\/TCBB.2006.58","volume":"3","author":"S Snir","year":"2006","unstructured":"Snir S, Rao S: Using max cut to enhance rooted trees consistency. IEEE\/ACM Trans Comput Biol Bioinformatics 2006, 3(4):323\u2013333.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinformatics"},{"key":"2398_CR7","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1177\/117693430600200003","volume":"2","author":"D Chen","year":"2006","unstructured":"Chen D, Eulenstein O, Fern\u00e1ndez-Baca D, Gordon Burleigh JG: Improved Heuristics for Minimum-Flip Supertree Construction. Evolutionary Bioinformatics 2006, 2: 401\u20134103.","journal-title":"Evolutionary Bioinformatics"},{"issue":"5","key":"2398_CR8","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1111\/j.1096-0031.2002.tb00289.x","volume":"18","author":"PA Golobo","year":"2002","unstructured":"Golobo3 PA, Pol D: Semi-strict supertrees. Cladistics 2002, 18(5):514\u2013525.","journal-title":"Cladistics"},{"key":"2398_CR9","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1111\/j.1096-0031.2005.00064.x","volume":"21","author":"PA Goloboff","year":"2005","unstructured":"Goloboff PA: Minority-rule supertrees? MRP, Compatibility, and MinFlip may display the least frequent groups. Cladistics 2005, 21: 282\u2013294.","journal-title":"Cladistics"},{"issue":"2","key":"2398_CR10","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1080\/10635150500481556","volume":"55","author":"JA Cotton","year":"2006","unstructured":"Cotton JA, Slater CSC, Wilkinson M: Discriminating Supported and Unsupported Relationships in Supertrees using Triplets. Syst Biol 2006, 55(2):345\u2013350.","journal-title":"Syst Biol"},{"key":"2398_CR11","first-page":"205","volume-title":"Proceedings of CPM, of LNCS","author":"V Berry","year":"2004","unstructured":"Berry V, Nicolas F: Maximum Agreement and Compatible Supertrees. In Proceedings of CPM, of LNCS Edited by: Sahinalp SC, Muthukrishnan S, Dogrusoz U. 2004, 3109: 205\u2013219."},{"issue":"3","key":"2398_CR12","first-page":"564","volume":"5","author":"V Berry","year":"2007","unstructured":"Berry V, Nicolas F: Maximum Agreement and Compatible Supertrees. JDA 2007, 5(3):564\u2013591.","journal-title":"JDA"},{"issue":"5","key":"2398_CR13","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1080\/10635150701639754","volume":"56","author":"V Ranwez","year":"2007","unstructured":"Ranwez V, Berry V, Criscuolo A, Fabre PH, Guillemot S, Scornavacca C, Douzery EPJ: PhySIC: a Veto Supertree Method with Desirable Properties. Syst Biol 2007, 56(5):798\u2013817.","journal-title":"Syst Biol"},{"key":"2398_CR14","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/BF01894195","volume":"3","author":"AG Gordon","year":"1986","unstructured":"Gordon AG: Consensus supertrees: the synthesis of rooted trees containing overlapping sets of labelled leaves. J Classif 1986, 3: 335\u2013348.","journal-title":"J Classif"},{"issue":"3\u20134","key":"2398_CR15","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1089\/106652799318337","volume":"6","author":"DH Huson","year":"1999","unstructured":"Huson DH, Nettles SM, Warnow TJ: Disk-covering, a fast-converging method for phylogenetic tree reconstruction. J Comput Biol 1999, 6(3\u20134):369\u2013386.","journal-title":"J Comput Biol"},{"key":"2398_CR16","first-page":"91","volume-title":"Advances in Data Science and Classification. Studies in Classification, Data Analysis, and Knowledge Organization","author":"J Thorley","year":"1998","unstructured":"Thorley J, Wilkinson M, Charleston M: The information content of consensus trees. In Advances in Data Science and Classification. Studies in Classification, Data Analysis, and Knowledge Organization Edited by: Rizzi A, Vichi M, Bock HH. 1998, 91\u201398."},{"key":"2398_CR17","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1186\/1471-2105-7-188","volume":"7","author":"J Dutheil","year":"2006","unstructured":"Dutheil J, Gaillard S, Bazin E, Glemin S, Ranwez V, Galtier N, Belkhir K: Bio++: a set of C++ libraries for sequence analysis, phylogenetics, molecular evolution and population genetics. BMC Bioinformatics 2006, 7: 188.","journal-title":"BMC Bioinformatics"},{"issue":"5","key":"2398_CR18","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1080\/10635150600969872","volume":"55","author":"A Criscuolo","year":"2006","unstructured":"Criscuolo A, Berry V, Douzery EJP, Gascuel O: SDM: a Fast Distance-based Approach for (Super)Tree Building in Phylogenomics. Syst Biol 2006, 55(5):740\u2013755.","journal-title":"Syst Biol"},{"issue":"2","key":"2398_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01731581","volume":"16","author":"M Kimura","year":"1980","unstructured":"Kimura M: A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences. J Mol Evol 1980, 16(2):111\u201320.","journal-title":"J Mol Evol"},{"key":"2398_CR20","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1080\/10635150490423719","volume":"53","author":"O Eulenstein","year":"2004","unstructured":"Eulenstein O, Chen D, Burleigh JG, Fern\u00e1ndez-Baca D, Sanderson MJ: Performance of flip supertree construction with a heuristic algorithm. Syst Biol 2004, 53: 299\u2013308.","journal-title":"Syst Biol"},{"issue":"5","key":"2398_CR21","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1080\/10635150390235520","volume":"52","author":"S Guindon","year":"2003","unstructured":"Guindon S, Gascuel O: A simple, fast and accurate method to estimate large phylogenies by maximum-likelihood. Syst Biol 2003, 52(5):696\u2013704.","journal-title":"Syst Biol"},{"key":"2398_CR22","doi-asserted-by":"publisher","first-page":"241+","DOI":"10.1186\/1471-2148-7-241","volume":"7","author":"V Ranwez","year":"2007","unstructured":"Ranwez V, Delsuc F, Ranwez S, Belkhir K, Tilak M, Douzery EPJ: OrthoMaM: A database of orthologous genomic markers for placental mammal phylogenetics. BMC Evol Biol 2007, 7: 241+. [http:\/\/kimura.univ-montp2.fr\/orthomam\/html\/]","journal-title":"BMC Evol Biol"},{"key":"2398_CR23","volume-title":"Version 4","author":"DL Swofford","year":"2003","unstructured":"Swofford DL: PAUP*. Phylogenetic Analysis Using Parsimony (*and Other Methods). In Version 4. Sinauer Associates, Sunderland, Massachusetts; 2003."},{"issue":"9","key":"2398_CR24","doi-asserted-by":"publisher","first-page":"2059","DOI":"10.1093\/molbev\/msm136","volume":"24","author":"BM Hallstrom","year":"2007","unstructured":"Hallstrom BM, Kullberg M, Nilsson MA, Janke A: Phylogenomic Data Analyses Provide Evidence that Xenarthra and Afrotheria Are Sister Groups. Mol Biol Evol 2007, 24(9):2059\u20132068.","journal-title":"Mol Biol Evol"},{"issue":"4","key":"2398_CR25","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1101\/gr.5918807","volume":"17","author":"WJ Murphy","year":"2007","unstructured":"Murphy WJ, Pringle TH, Crider TA, Springer MS, Miller W: Using genomic data to unravel the root of the placental mammal phylogeny. Genome Res 2007, 17(4):413\u2013421.","journal-title":"Genome Res"},{"issue":"36","key":"2398_CR26","doi-asserted-by":"publisher","first-page":"14395","DOI":"10.1073\/pnas.0704342104","volume":"104","author":"DE Wildman","year":"2007","unstructured":"Wildman DE, Uddin M, Opazo JC, Liu G, Lefort V, Guindon S, Gascuel O, Grossman LI, Romero R, Goodman M: Genomics, biogeography, and the diversification of placental mammals. Proc Nat Acad Sci 2007, 104(36):14395\u201314400.","journal-title":"Proc Nat Acad Sci"},{"key":"2398_CR27","volume-title":"Philos Trans R Soc Lond B Biol Sci","author":"N Lartillot","year":"2008","unstructured":"Lartillot N, Philippe H: Improvement of molecular phylogenetic inference and the phylogeny of Bilateria. Philos Trans R Soc Lond B Biol Sci 2008. [0962\u20138436 (Print) Journal article]"},{"key":"2398_CR28","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/1471-2148-4-18","volume":"4","author":"G Jobb","year":"2004","unstructured":"Jobb G, von Haeseler A, Strimmer K: TREEFINDER: a powerful graphical analysis environment for molecular phylogenetics. BMC Evol Biol 2004, 4: 18. [1471\u20132148 (Electronic) Journal Article Research Support, Non-U.S. Gov't]","journal-title":"BMC Evol Biol"},{"issue":"7188","key":"2398_CR29","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1038\/nature06614","volume":"452","author":"CW Dunn","year":"2008","unstructured":"Dunn CW, Hejnol A, Matus DQ, Pang K, Browne WE, Smith SA, Seaver E, Rouse GW, Obst M, Edgecombe GD, Sorensen MV, Haddock SHD, Schmidt-Rhaesa A, Okusu A, Kristensen RM, Wheeler WC, Martindale MQ, Giribet G: Broad phylogenomic sampling improves resolution of the animal tree of life. Nature 2008, 452(7188):745-U5.","journal-title":"Nature"},{"key":"2398_CR30","volume-title":"Phylogenetics, of Oxford Lecture Series in Mathematics and its Applications","author":"C Semple","year":"2003","unstructured":"Semple C, Steel MA: Phylogenetics, of Oxford Lecture Series in Mathematics and its Applications. Volume 24. Oxford University Press; 2003."},{"key":"2398_CR31","volume-title":"Finding a largest subset of rooted triples identifying a tree is an NP-hard task","author":"S Guillemot","year":"2007","unstructured":"Guillemot S, Berry V: Finding a largest subset of rooted triples identifying a tree is an NP-hard task. Tech rep, LIRMM, Univ Montpellier; 2007."},{"key":"2398_CR32","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1023\/B:JOCO.0000021936.04215.68","volume":"29","author":"BY Wu","year":"2004","unstructured":"Wu BY: Constructing the maximum consensus tree from rooted triples. Journal of Combinatorial Optimization 2004, 29: 29\u201339.","journal-title":"Journal of Combinatorial Optimization"},{"key":"2398_CR33","first-page":"50","volume":"7","author":"J Jansson","year":"2001","unstructured":"Jansson J: On the complexity of inferring rooted evolutionary trees. Proceedings of GRACO 2001 Electron Notes in Disc Math 2001, 7: 50\u201353.","journal-title":"Proceedings of GRACO 2001 Electron Notes in Disc Math"},{"key":"2398_CR34","volume-title":"PhD thesis","author":"D Bryant","year":"1997","unstructured":"Bryant D: Building Trees, Hunting for Trees, and Comparing Trees: theory and method in phylogenetic analysis. PhD thesis. University of Canterbury; 1997."},{"key":"2398_CR35","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1080\/106351502753475862","volume":"51","author":"J Huelsenbeck","year":"2002","unstructured":"Huelsenbeck J, Bollback J, Levine A: Inferring the root of a phylogenetic tree. Syst Biol 2002, 51: 32\u201343.","journal-title":"Syst Biol"},{"issue":"3","key":"2398_CR36","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"AV Aho","year":"1981","unstructured":"Aho AV, Sagiv Y, Szymanski TG, Ullman JD: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J Comp 1981, 10(3):405\u2013421.","journal-title":"SIAM J Comp"},{"key":"2398_CR37","volume-title":"The analysis of cross-classified categorical data","author":"SE Fienberg","year":"1977","unstructured":"Fienberg SE: The analysis of cross-classified categorical data. Cambridge, MA: MIT Press; 1977."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-413.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T03:36:06Z","timestamp":1630467366000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-413"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,4]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2398"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-413","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,4]]},"assertion":[{"value":"29 January 2008","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"413"}}