{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:24:44Z","timestamp":1773275084164,"version":"3.50.1"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3065,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences.<\/jats:p><jats:p>Results: We present in this article a distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data.<\/jats:p><jats:p>Availability: The Perl package Bio::PhyloNetwork, included in the BioPerl bundle, implements many algorithms on phylogenetic networks, including the computation of the distance presented in this article.<\/jats:p><jats:p>Contact: \u00a0gabriel.cardona@uib.es<\/jats:p><jats:p>Supplementary information: Some counterexamples, proofs of the results not included in this article, and some computational experiments are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn231","type":"journal-article","created":{"date-parts":[[2008,5,14]],"date-time":"2008-05-14T00:14:07Z","timestamp":1210724047000},"page":"1481-1488","source":"Crossref","is-referenced-by-count":50,"title":["A distance metric for a class of tree-sibling phylogenetic networks"],"prefix":"10.1093","volume":"24","author":[{"given":"Gabriel","family":"Cardona","sequence":"first","affiliation":[{"name":"1 Department of Mathematics and Computer Science, University of the Balearic Islands, E-07122 Palma de Mallorca and 2Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, E-08034 Barcelona, Spain"}]},{"given":"Merc\u00e8","family":"Llabr\u00e9s","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science, University of the Balearic Islands, E-07122 Palma de Mallorca and 2Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, E-08034 Barcelona, Spain"}]},{"given":"Francesc","family":"Rossell\u00f3","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science, University of the Balearic Islands, E-07122 Palma de Mallorca and 2Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, E-08034 Barcelona, Spain"}]},{"given":"Gabriel","family":"Valiente","sequence":"additional","affiliation":[{"name":"1 Department of Mathematics and Computer Science, University of the Balearic Islands, E-07122 Palma de Mallorca and 2Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, E-08034 Barcelona, Spain"}]}],"member":"286","published-online":{"date-parts":[[2008,5,12]]},"reference":[{"key":"2023020210373091200_B1","first-page":"133","article-title":"Weak hierarchies associated with similarity measures\u2014an additive clustering technique","volume":"51","author":"Bandelt","year":"1986","journal-title":"Bull. Math. Biol."},{"key":"2023020210373091200_B2","first-page":"51","article-title":"Phylogenetic networks","volume":"34","author":"Bandelt","year":"1994","journal-title":"Verh. Naturwiss. Ver. Hambg."},{"key":"2023020210373091200_B3","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1080\/10635150500431197","article-title":"Hybrids in real time","volume":"55","author":"Baroni","year":"2006","journal-title":"Syst. Biol."},{"key":"2023020210373091200_B4","first-page":"320","volume-title":"Phylogenetic networks based on the molecular clock hypothesis","author":"Bereg","year":"2005"},{"key":"2023020210373091200_B5","volume-title":"The Correspondence of Charles Darwin","author":"Burkhardt","year":"1987"},{"key":"2023020210373091200_B6","article-title":"Comparison of tree-child phylogenetic networks","volume-title":"IEEE T. Comput. Biol.","author":"Cardona","year":"2007"},{"key":"2023020210373091200_B7","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1186\/1471-2105-9-175","article-title":"A perl package and an alignment tool for phylogenetic networks","volume":"9","author":"Cardona","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023020210373091200_B8","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.mbs.2007.11.003","article-title":"Tripartitions do not always discriminate phylogenetic networks","volume":"211","author":"Cardona","year":"2008","journal-title":"Math. Biosci."},{"key":"2023020210373091200_B9","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/B978-0-444-87877-9.50038-8","article-title":"An extension of hierarchical clustering: the pyramidal representation","volume-title":"Pattern Recognition in Practice","author":"Diday","year":"1986"},{"key":"2023020210373091200_B10","doi-asserted-by":"crossref","first-page":"2124","DOI":"10.1126\/science.284.5423.2124","article-title":"Phylogenetic classification and the universal tree","volume":"284","author":"Doolittle","year":"1999","journal-title":"Science"},{"key":"2023020210373091200_B11","article-title":"GCB 2006 \u2013 Tutorial: Introduction to phylogenetic networks. Tutorial presented at the German Conference on Bioinformatics (GCB'06)","author":"Huson","year":"2006"},{"key":"2023020210373091200_B12","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/oso\/9780199208227.003.0009","article-title":"Split networks and reticulate networks","volume-title":"Reconstructing Evolution: New Mathematical and Computational Advances","author":"Huson","year":"2007"},{"key":"2023020210373091200_B13","doi-asserted-by":"crossref","first-page":"2604","DOI":"10.1093\/bioinformatics\/btl452","article-title":"Maximum likelihood of phylogenetic networks","volume":"22","author":"Jin","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020210373091200_B14","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1093\/bioinformatics\/btl313","article-title":"Efficient parsimony-based methods for phylogenetic network reconstruction","volume":"23","author":"Jin","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210373091200_B15","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1093\/molbev\/msl163","article-title":"Inferring phylogenetic networks by the maximum parsimony criterion: a case study","volume":"24","author":"Jin","year":"2007","journal-title":"Mol. Biol. Evol."},{"key":"2023020210373091200_B16","article-title":"Network (reticulate) evolution: biology, models and algorithms","volume-title":"Tutorial presented at the Ninth Pacific Symposium on Biocomputing","author":"Linder","year":"2003"},{"key":"2023020210373091200_B17","first-page":"13","article-title":"Phylogenetic Networks: modeling, reconstructibility, and accuracy","volume":"1","author":"Moret","year":"2004","journal-title":"IEEE T. Comput. Biol."},{"key":"2023020210373091200_B18","article-title":"Phylogenetic Networks","volume-title":"PhD Thesis","author":"Nakhleh","year":"2004"},{"key":"2023020210373091200_B19","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1038\/44766","article-title":"Inferring the historical patterns of biological evolution","volume":"401","author":"Pagel","year":"1999","journal-title":"Nature"},{"key":"2023020210373091200_B20","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1093\/oso\/9780199208227.003.0010","article-title":"Hybridization networks","volume-title":"Reconstructing Evolution: New Mathematical and Computational Advances","author":"Semple","year":"2007"},{"key":"2023020210373091200_B21","doi-asserted-by":"crossref","first-page":"1611","DOI":"10.1101\/gr.361602","article-title":"The BioPerl toolkit: Perl modules for the life sciences","volume":"12","author":"Stajich","year":"2002","journal-title":"Genome Res."},{"key":"2023020210373091200_B22","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1093\/oxfordjournals.molbev.a026367","article-title":"Likelihood analysis of phylogenetic networks using directed graphical models","volume":"17","author":"Strimmer","year":"2000","journal-title":"Mol. Biol. Evol."},{"key":"2023020210373091200_B23","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/oxfordjournals.molbev.a003725","article-title":"Recombination analysis using directed graphical models","volume":"18","author":"Strimmer","year":"2001","journal-title":"Mol. Biol. Evol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/1481\/49053118\/bioinformatics_24_13_1481.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/1481\/49053118\/bioinformatics_24_13_1481.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T06:52:23Z","timestamp":1708930343000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/1481\/238641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,12]]},"references-count":23,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn231","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,5,12]]}}}