{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T09:53:51Z","timestamp":1726221231215},"reference-count":34,"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":[[2013,12]]},"abstract":"Abstract<\/jats:title>Background<\/jats:title>Phylogenetic tree comparison metrics are an important tool in the study of evolution, and hence the definition of such metrics is an interesting problem in phylogenetics. In a paper in Taxon fifty years ago, Sokal and Rohlf proposed to measure quantitatively the difference between a pair of phylogenetic trees by first encoding them by means of their half-matrices of cophenetic values, and then comparing these matrices. This idea has been used several times since then to define dissimilarity measures between phylogenetic trees but, to our knowledge, no proper metric on weighted phylogenetic trees with nested taxa based on this idea has been formally defined and studied yet. Actually, the cophenetic values of pairs of different taxa alone are not enough to single out phylogenetic trees with weighted arcs or nested taxa.<\/jats:p><\/jats:sec>Results<\/jats:title>For every (rooted) phylogenetic treeT<\/jats:italic>, let itscophenetic vector<\/jats:italic>\u03c6<\/jats:italic>(T<\/jats:italic>) consist of all pairs of cophenetic values between pairs of taxa inT<\/jats:italic>and all depths of taxa inT<\/jats:italic>. It turns out that these cophenetic vectors single out weighted phylogenetic trees with nested taxa. We then define a family of cophenetic metricsd<\/jats:italic>\u03c6<\/jats:italic>,p<\/jats:italic><\/jats:sub>by comparing these cophenetic vectors by means ofL<\/jats:italic>p<\/jats:italic><\/jats:sup>norms, and we study, either analytically or numerically, some of their basic properties: neighbors, diameter, distribution, and their rank correlation with each other and with other metrics.<\/jats:p><\/jats:sec>Conclusions<\/jats:title>The cophenetic metrics can be safely used on weighted phylogenetic trees with nested taxa and no restriction on degrees, and they can be computed inO<\/jats:italic>(n<\/jats:italic>2<\/jats:sup>) time, wheren<\/jats:italic>stands for the number of taxa. The metricsd<\/jats:italic>\u03c6<\/jats:italic>,1<\/jats:sub>andd<\/jats:italic>\u03c6<\/jats:italic>,2<\/jats:sub>have positive skewed distributions, and they show a low rank correlation with the Robinson-Foulds metric and the nodal metrics, and a very high correlation with each other and with the splitted nodal metrics. The diameter ofd<\/jats:italic>\u03c6<\/jats:italic>,p<\/jats:italic><\/jats:sub>, forp<\/mml:mi>\u2a7e<\/mml:mo>1<\/mml:mn><\/mml:math><\/jats:inline-formula>, is inO<\/jats:italic>(n<\/jats:italic>(p<\/jats:italic>+2)\/p<\/jats:italic><\/jats:sup>), and thus for lowp<\/jats:italic>they are more discriminative, having a wider range of values.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1471-2105-14-3","type":"journal-article","created":{"date-parts":[[2013,1,16]],"date-time":"2013-01-16T11:20:00Z","timestamp":1358335200000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":39,"title":["Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf"],"prefix":"10.1186","volume":"14","author":[{"given":"Gabriel","family":"Cardona","sequence":"first","affiliation":[]},{"given":"Arnau","family":"Mir","sequence":"additional","affiliation":[]},{"given":"Francesc","family":"Rossell\u00f3","sequence":"additional","affiliation":[]},{"given":"Luc\u00eda","family":"Rotger","sequence":"additional","affiliation":[]},{"given":"David","family":"S\u00e1nchez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,16]]},"reference":[{"key":"5975_CR1","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1109\/MCSE.2005.55","volume":"7","author":"K Hoef-Emden","year":"2005","unstructured":"Hoef-Emden K: Molecular phylogenetic analyses and real-life data. Comput Sci Eng. 2005, 7: 86-91. 10.1109\/MCSE.2005.55.","journal-title":"Comput Sci Eng"},{"key":"5975_CR2","volume-title":"Inferring Phylogenies","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein J: Inferring Phylogenies. 2004, USA: Sinauer Associates Inc."},{"key":"5975_CR3","doi-asserted-by":"publisher","first-page":"459","DOI":"10.2307\/2413054","volume":"30","author":"F Rohlf","year":"1981","unstructured":"Rohlf F, Sokal R: Comparing numerical taxonomic studies. Syst Zool. 1981, 30: 459-490. 10.2307\/2413054.","journal-title":"Syst Zool"},{"key":"5975_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.2307\/1217208","volume":"11","author":"R Sokal","year":"1962","unstructured":"Sokal R, Rohlf F: The Comparison of Dendrograms by Objective Methods. Taxon. 1962, 11: 33-40. 10.2307\/1217208.","journal-title":"Taxon"},{"key":"5975_CR5","doi-asserted-by":"publisher","first-page":"519","DOI":"10.2307\/1218253","volume":"20","author":"WT Williams","year":"1971","unstructured":"Williams WT, Clifford HT: On the comparison of two classifications of the same set of elements. Taxon. 1971, 20: 519-522. 10.2307\/1218253.","journal-title":"Taxon"},{"key":"5975_CR6","doi-asserted-by":"publisher","first-page":"3201","DOI":"10.1093\/bioinformatics\/bti517","volume":"21","author":"J Handl","year":"2005","unstructured":"Handl J, Knowles J, Kell DB: Computational cluster validation in post-genomic data analysis. Bioinformatics. 2005, 21: 3201-3212. 10.1093\/bioinformatics\/bti517.","journal-title":"Bioinformatics"},{"key":"5975_CR7","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1021\/ci6005189","volume":"47","author":"G Restrepo","year":"2007","unstructured":"Restrepo G, Mesa H, Llanos E: Three Dissimilarity Measures to Contrast Dendrograms. J Chem Inf Model. 2007, 47: 761-770. 10.1021\/ci6005189.","journal-title":"J Chem Inf Model"},{"key":"5975_CR8","first-page":"126","volume":"42","author":"MA Steel","year":"1993","unstructured":"Steel MA, Penny D: Distributions of tree comparison metrics\u2014some new results. Syst Biol. 1993, 42: 126-141.","journal-title":"Syst Biol"},{"key":"5975_CR9","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/0022-5193(78)90137-6","volume":"73","author":"MS Waterman","year":"1978","unstructured":"Waterman MS, Smith TF: On the similarity of dendrograms. J Theor Biol. 1978, 73: 789-800. 10.1016\/0022-5193(78)90137-6.","journal-title":"J Theor Biol"},{"key":"5975_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"BL Allen","year":"2001","unstructured":"Allen BL, Steel MA: Subtree transfer operations and their induced metrics on evolutionary trees. Ann Combinatorics. 2001, 5: 1-13. 10.1007\/s00026-001-8006-8.","journal-title":"Ann Combinatorics"},{"key":"5975_CR11","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"C Finden","year":"1985","unstructured":"Finden C, Gordon A: Obtaining common pruned trees. J Classification. 1985, 2: 255-276. 10.1007\/BF01908078.","journal-title":"J Classification"},{"key":"5975_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0025-5564(94)90012-4","volume":"123","author":"W Goddard","year":"1994","unstructured":"Goddard W, Kubicka E, Kubicki G, McMorris F: The agreement metric for labeled binary trees. Math Biosci. 1994, 123: 215-226. 10.1016\/0025-5564(94)90012-4.","journal-title":"Math Biosci"},{"key":"5975_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0303-2647(97)01684-5","volume":"42","author":"Y Zhong","year":"1997","unstructured":"Zhong Y, Meacham C, Pramanik S: A general method for tree-comparison based on subtree similarity and its use in a taxonomic database. Biosystems. 1997, 42: 1-8. 10.1016\/S0303-2647(97)01684-5.","journal-title":"Biosystems"},{"key":"5975_CR14","first-page":"119","volume-title":"Proc 6th Australian Conf Combinatorial Mathematics, Lecture Notes in Mathematics","author":"DF Robinson","year":"1979","unstructured":"Robinson DF, Foulds LR: Comparisonof weighted labelled trees. Proc 6th Australian Conf Combinatorial Mathematics, Lecture Notes in Mathematics. 1979, Berlin Heidelberg: Springer, 119-126."},{"key":"5975_CR15","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"DF Robinson","year":"1981","unstructured":"Robinson DF, Foulds LR: Comparison of phylogenetic trees. Math Bioscie. 1981, 53: 131-147. 10.1016\/0025-5564(81)90043-2.","journal-title":"Math Bioscie"},{"key":"5975_CR16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1093\/sysbio\/45.3.323","volume":"45","author":"DE Critchlow","year":"1996","unstructured":"Critchlow DE, Pearl DK, Qian C: The triples distance for rooted bifurcating phylogenetic trees. Syst Biol. 1996, 45: 323-334. 10.1093\/sysbio\/45.3.323.","journal-title":"Syst Biol"},{"key":"5975_CR17","doi-asserted-by":"publisher","first-page":"374","DOI":"10.2307\/2412182","volume":"18","author":"JS Farris","year":"1969","unstructured":"Farris JS: A successive approximations approach to character weighting. Syst Zool. 1969, 18: 374-385. 10.2307\/2412182.","journal-title":"Syst Zool"},{"key":"5975_CR18","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/2412378","volume":"22","author":"JS Farris","year":"1973","unstructured":"Farris JS: On comparing the shapes of taxonomic trees. Syst Zool. 1973, 22: 50-54. 10.2307\/2412378.","journal-title":"Syst Zool"},{"key":"5975_CR19","doi-asserted-by":"publisher","first-page":"306","DOI":"10.2307\/2412343","volume":"20","author":"JB Phipps","year":"1971","unstructured":"Phipps JB: Dendrogram topology. Syst Zool. 1971, 20: 306-308. 10.2307\/2412343.","journal-title":"Syst Zool"},{"key":"5975_CR20","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00285-009-0295-2","volume":"61","author":"G Cardona","year":"2010","unstructured":"Cardona G, Llabr\u00e9s M, Rossell\u00f3 F, Valiente G: Nodal distances for rooted phylogenetic trees. J Math Biol. 2010, 61: 253-276. 10.1007\/s00285-009-0295-2.","journal-title":"J Math Biol"},{"key":"5975_CR21","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1093\/sysbio\/17.4.388","volume":"17","author":"N Basford","year":"1968","unstructured":"Basford N, Butler J, Leone C, Rohlf F: Immunologic Comparisons of Selected Coleoptera With Analyses of Relationships Using Numerical Taxonomic Methods. Syst Biol. 1968, 17: 388-406. 10.1093\/sysbio\/17.4.388.","journal-title":"Syst Biol"},{"key":"5975_CR22","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1093\/sysbio\/21.1.7","volume":"21","author":"V Chui","year":"1972","unstructured":"Chui V, Thornton I: A Numerical Taxonomic Study of the Endemic Ptycta Species of the Hawaiian Islands (Psocoptera: Psocidae). Syst Biol. 1972, 21: 7-22. 10.1093\/sysbio\/21.1.7.","journal-title":"Syst Biol"},{"key":"5975_CR23","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1080\/11263504.2011.610924","volume":"145","author":"M Leelambikaa","year":"2011","unstructured":"Leelambikaa M, Sathyanarayanaa N: Genetic characterization of Indian Mucuna (Leguminoceae) species using morphometric and random amplification of polymorphic DNA (RAPD) approaches. Plant Biosystems. 2011, 145: 786-797. 10.1080\/11263504.2011.610924.","journal-title":"Plant Biosystems"},{"key":"5975_CR24","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1080\/01621459.1967.10500922","volume":"62","author":"J Hartigan","year":"1967","unstructured":"Hartigan J: Representation of similarity matrices by trees. J Am Stat Assoc. 1967, 62: 1140-1158. 10.1080\/01621459.1967.10500922.","journal-title":"J Am Stat Assoc"},{"key":"5975_CR25","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198546412.001.0001","volume-title":"The comparative method in evolutionary biology","author":"PH Harvey","year":"1991","unstructured":"Harvey PH, Pagel M: The comparative method in evolutionary biology. 1991, USA: Oxford university press"},{"key":"5975_CR26","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1038\/44766","volume":"401","author":"MD Pagel","year":"1999","unstructured":"Pagel MD: Inferring the Historical Patterns of Biological Evolution. Nature. 1999, 401: 877-884. 10.1038\/44766.","journal-title":"Nature"},{"key":"5975_CR27","doi-asserted-by":"publisher","first-page":"172","DOI":"10.2307\/2412452","volume":"19","author":"JS Farris","year":"1970","unstructured":"Farris JS, Kluge AG, Eckardt MJ: A numerical approach to phylogenetic systematics. Syst Zool. 1970, 19: 172-189. 10.2307\/2412452.","journal-title":"Syst Zool"},{"key":"5975_CR28","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02289588","volume":"32","author":"SC Johnson","year":"1967","unstructured":"Johnson SC: Hierarchical clustering schemes. Psychometrika. 1967, 32: 241-254. 10.1007\/BF02289588.","journal-title":"Psychometrika"},{"key":"5975_CR29","volume-title":"Numerical Taxonomy","author":"P Sneath","year":"1973","unstructured":"Sneath P, Sokal R: Numerical Taxonomy. 1973, USA: Freeman and Co"},{"key":"5975_CR30","first-page":"949","volume":"11","author":"S Xu","year":"1994","unstructured":"Xu S, Atchley WR, Fitch WM: Phylogenetic Iinference under the pure drift model. Mol Biol Evol. 1994, 11: 949-960.","journal-title":"Mol Biol Evol"},{"key":"5975_CR31","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C Semple","year":"2003","unstructured":"Semple C, Steel M: Phylogenetics. 2003, USA: Oxford University Press"},{"key":"5975_CR32","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1137\/0401050","volume":"1","author":"M Steel","year":"1988","unstructured":"Steel M: Distribution of the symmetric difference metric on phylogenetic trees. SIAM J Discrete Mathematics. 1988, 1: 541-551. 10.1137\/0401050.","journal-title":"SIAM J Discrete Mathematics"},{"key":"5975_CR33","doi-asserted-by":"publisher","first-page":"1320","DOI":"10.1016\/j.aml.2009.03.003","volume":"22","author":"R Alberich","year":"2009","unstructured":"Alberich R, Cardona G, Rossell\u00f3 F, Valiente G: An algebraic metric for phylogenetic trees. Appl Mathematics Lett. 2009, 22: 1320-1324. 10.1016\/j.aml.2009.03.003.","journal-title":"Appl Mathematics Lett"},{"key":"5975_CR34","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1006\/aama.2001.0759","volume":"27","author":"LJ Billera","year":"2001","unstructured":"Billera LJ, Holmes SP, Vogtmann K: Geometry of the space of phylogenetic trees. Adv Appl Mathematics. 2001, 27: 733-767. 10.1006\/aama.2001.0759.","journal-title":"Adv Appl Mathematics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-14-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T19:38:33Z","timestamp":1714851513000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-14-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,16]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["5975"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-14-3","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,16]]},"assertion":[{"value":"17 July 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}