{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T06:05:12Z","timestamp":1750313112559},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"S2","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time <jats:italic>O<\/jats:italic> (<jats:italic>n<\/jats:italic> log<jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time <jats:italic>O<\/jats:italic> (<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to <jats:italic>O<\/jats:italic> (<jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.<\/jats:p>","DOI":"10.1186\/1471-2105-14-s2-s18","type":"journal-article","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T15:15:57Z","timestamp":1358781357000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A practical O(n log2 n) time algorithm for computing the triplet distance on binary trees"],"prefix":"10.1186","volume":"14","author":[{"given":"Andreas","family":"Sand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian NS","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Mailund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,1,21]]},"reference":[{"key":"5607_CR1","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. Mathematical Biosciences. 1981, 53: 131-147. 10.1016\/0025-5564(81)90043-2.","journal-title":"Mathematical Biosciences"},{"issue":"3","key":"5607_CR2","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 CL: The triples distance for rooted bifurcating phylogenetic trees. Systematic Biology. 1996, 45 (3): 323-334. 10.1093\/sysbio\/45.3.323.","journal-title":"Systematic Biology"},{"issue":"2","key":"5607_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.2307\/2413326","volume":"34","author":"GF Estabrook","year":"1985","unstructured":"Estabrook GF, McMorris FR, Meacham CA: Comparison of Undirected Phylogenetic Trees Based on Subtrees of Four Evolutionary Units. Systematic Zoology. 1985, 34 (2): 193-10.2307\/2413326.","journal-title":"Systematic Zoology"},{"key":"5607_CR4","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01908061","volume":"2","author":"WHE Day","year":"1985","unstructured":"Day WHE: Optimal-Algorithms for Comparing Trees with Labeled Leaves. Journal of Classification. 1985, 2: 7-28. 10.1007\/BF01908061.","journal-title":"Journal of Classification"},{"issue":"2","key":"5607_CR5","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/s00453-003-1065-y","volume":"38","author":"GS Brodal","year":"2004","unstructured":"Brodal GS, Fagerberg R, Pedersen CNS: Computing the quartet distance between evolutionary trees in time O(n log n). Algorithmica. 2004, 38 (2): 377-395. 10.1007\/s00453-003-1065-y.","journal-title":"Algorithmica"},{"key":"5607_CR6","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1142\/9781860947995_0013","volume-title":"Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC)","author":"MS Stissing","year":"2007","unstructured":"Stissing MS, Pedersen CNS, Mailund T, Brodal GS, Fagerberg R: Computing the quartet distance between evolutionary trees of bounded degree. Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC). 2007, Imperial College Press, 101-110."},{"key":"5607_CR7","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1186\/1748-7188-6-15","volume":"6","author":"J Nielsen","year":"2011","unstructured":"Nielsen J, Kristensen A, Mailund T, Pedersen CNS: A sub-cubic time algorithm for computing the quartet distance between two general trees. Algorithms for Molecular Biology. 2011, 6: 15-10.1186\/1748-7188-6-15.","journal-title":"Algorithms for Molecular Biology"},{"key":"5607_CR8","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1186\/1748-7188-1-16","volume":"1","author":"C Christiansen","year":"2006","unstructured":"Christiansen C, Mailund T, Pedersen CNS, Randers M, Stissing MS: Fast calculation of the quartet distance between trees of arbitrary degrees. Algorithms Mol Biol. 2006, 1: 16-10.1186\/1748-7188-1-16.","journal-title":"Algorithms Mol Biol"},{"issue":"48","key":"5607_CR9","doi-asserted-by":"publisher","first-page":"6634","DOI":"10.1016\/j.tcs.2011.08.027","volume":"412","author":"MS Bansal","year":"2011","unstructured":"Bansal MS, Dong J, Fern\u00e1ndez-Baca D: Comparing and aggregating partially resolved trees. Theoretical Computer Science. 2011, 412 (48): 6634-6652. 10.1016\/j.tcs.2011.08.027.","journal-title":"Theoretical Computer Science"},{"issue":"10","key":"5607_CR10","doi-asserted-by":"publisher","first-page":"1636","DOI":"10.1093\/bioinformatics\/bth097","volume":"20","author":"T Mailund","year":"2004","unstructured":"Mailund T, Pedersen CNS: QDist-quartet distance between evolutionary trees. Bioinformatics. 2004, 20 (10): 1636-1637. 10.1093\/bioinformatics\/bth097.","journal-title":"Bioinformatics"},{"key":"5607_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1142\/S0219720008003266","volume":"6","author":"MS Stissing","year":"2008","unstructured":"Stissing MS, Mailund T, Pedersen CNS, Brodal GS, Fagerberg R: Computing the all-pairs quartet distance on a set of evolutionary trees. Journal of Bioinformatics and Computational Biology. 2008, 6: 37-50. 10.1142\/S0219720008003266.","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"5607_CR12","first-page":"285","volume-title":"Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms","author":"D Bryant","year":"2000","unstructured":"Bryant D, Tsang J, Kearney P, Li M: Computing the quartet distance between evolutionary trees. Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. 2000, 285-286. Society for Industrial and Applied Mathematics"},{"key":"5607_CR13","first-page":"731","volume-title":"Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC)","author":"GS Brodal","year":"2001","unstructured":"Brodal GS, Fagerberg R, Pedersen CNS: Computing the quartet distance between evolutionary trees in time O(n log2 n). Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC). 2001, Springer, 2223: 731-742. 10.1007\/3-540-45678-3_62. Lecture Notes in Computer Science"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-14-S2-S18.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:32:59Z","timestamp":1630531979000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-14-S2-S18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":13,"journal-issue":{"issue":"S2","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["5607"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-14-s2-s18","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]},"assertion":[{"value":"21 January 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S18"}}