{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T10:00:24Z","timestamp":1792058424880,"version":"4.4.0"},"reference-count":41,"publisher":"The Royal Society","issue":"1919","license":[{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/royalsociety.org\/-\/media\/journals\/author\/Licence-to-Publish-20062019-final.pdf"},{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/royalsociety.org\/journals\/ethics-policies\/data-sharing-mining\/"},{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/royalsociety.org\/-\/media\/journals\/author\/Licence-to-Publish-20062019-final.pdf"},{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/royalsociety.org\/journals\/ethics-policies\/data-sharing-mining\/"}],"funder":[{"name":"National Science and Technology Council"},{"DOI":"10.13039\/501100020950","name":"National Science and Technology Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100020950","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["royalsocietypublishing.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,2,13]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Shape parameters, e.g. balance indices, of evolutionary trees have been extensively studied under the Yule model in phylogenetics. Independently, many of the same parameters have also been studied for random binary search trees in computer science, where they measure the running time of algorithms. In fact, under the Yule and binary search tree models, these parameters have the same distribution, resulting in many identical discoveries. In this survey, we explain these connections and introduce some of the tools that have been used in computer science to derive stochastic results for shape parameters.<\/jats:p>\n                  <jats:p>This article is part of the theme issue \u2018\u201cA mathematical theory of evolution\u201d: phylogenetic models dating back 100 years\u2019.<\/jats:p>","DOI":"10.1098\/rstb.2023.0304","type":"journal-article","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T08:46:46Z","timestamp":1740041206000},"update-policy":"https:\/\/doi.org\/10.1098\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Shape parameters of evolutionary trees in theoretical computer science"],"prefix":"10.1098","volume":"380","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8891-6897","authenticated-orcid":true,"given":"Michael","family":"Fuchs","sequence":"first","affiliation":[{"name":"Taipei 116, Taiwan 1","department":["Department of Mathematical Sciences, National Chengchi University,"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"175","published-online":{"date-parts":[[2025,2,20]]},"reference":[{"key":"2026010107152412500_B1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"Semple","year":"2003"},{"key":"2026010107152412500_B2","volume-title":"Phylogeny\u2014discrete and random processes in evolution (CBMS-NSF regional conference series in applied mathematics vol. 89)","author":"Steel","year":"2016"},{"key":"2026010107152412500_B3","first-page":"21","article-title":"A mathematical theory of evolution based on the conclusions of Dr. J. C. Willis, F.R.S","volume":"213","author":"Yule","year":"1925","journal-title":"Phil. Trans. R. Soc. B"},{"key":"2026010107152412500_B4","doi-asserted-by":"crossref","first-page":"44","DOI":"10.2307\/1426329","article-title":"The probabilities of rooted tree-shapes generated by random bifurcation","volume":"3","author":"Harding","year":"1971","journal-title":"Adv. Appl. Probab."},{"key":"2026010107152412500_B5","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1080\/0025570X.2023.2266389","article-title":"A mathematical connection between single-elimination sports tournaments and evolutionary trees","volume":"96","author":"King","year":"2023","journal-title":"Math. Mag."},{"key":"2026010107152412500_B6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0304-4149(82)90011-4","article-title":"The coalescent","volume":"13","author":"Kingman","year":"1982","journal-title":"Stoch. Process. Appl."},{"key":"2026010107152412500_B7","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-031-39800-1_25","volume-title":"Tree balance indices: a comprehensive survey","author":"Fischer","year":"2023","edition":"1st"},{"key":"2026010107152412500_B8","doi-asserted-by":"crossref","first-page":"102594","DOI":"10.1016\/j.aam.2023.102594","article-title":"The distributions under two species-tree models of the total number of ancestral configurations for matching gene trees and species trees","volume":"152","author":"Disanto","year":"2024","journal-title":"Adv. Appl. Math."},{"key":"2026010107152412500_B9","first-page":"4426","article-title":"The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees","volume":"32","author":"Disanto","year":"2023","journal-title":"Ann. Appl. Probab."},{"key":"2026010107152412500_B10","volume-title":"The art of computer programming, vol. iii: sorting and searching","author":"Knuth","year":"1998","edition":"2nd"},{"key":"2026010107152412500_B11","volume-title":"Evolution of random search trees","author":"Mahmoud","year":"1992"},{"key":"2026010107152412500_B12","volume-title":"An introduction to the analysis of algorithms","author":"Flajolet","year":"2013","edition":"2nd"},{"key":"2026010107152412500_B13","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/(SICI)1098-2418(199710)11:3<223::AID-RSA2>3.0.CO;2-2","article-title":"Patterns in random binary search trees","volume":"11","author":"Flajolet","year":"1997","journal-title":"Random Struct. Algorithms"},{"key":"2026010107152412500_B14","doi-asserted-by":"crossref","first-page":"2195","DOI":"10.1214\/105051606000000547","article-title":"The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance","volume":"16","author":"Blum","year":"2006","journal-title":"Ann. Appl. Probab."},{"key":"2026010107152412500_B15","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/3-540-55251-0_2","article-title":"Varieties of increasing trees","volume":"581","author":"Bergeron","year":"1992","journal-title":"Lect. Notes Comput. Sci."},{"key":"2026010107152412500_B16","doi-asserted-by":"crossref","first-page":"1687","DOI":"10.1137\/S009753970138390X","article-title":"Phase change of limit laws in the quicksort recurrence under varying toll functions","volume":"31","author":"Hwang","year":"2002","journal-title":"SIAM J. Comput."},{"key":"2026010107152412500_B17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/22-EJP776","article-title":"Central limit theorems for additive functionals and fringe trees in tries","volume":"27","author":"Janson","year":"2022","journal-title":"Electron. J. Probab."},{"key":"2026010107152412500_B18","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1017\/S0963548314000443","article-title":"Central limit theorems for additive tree parameters with small toll functions","volume":"24","author":"Wagner","year":"2015","journal-title":"Comb. Probab. Comput."},{"key":"2026010107152412500_B19","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1214\/EJP.v16-885","article-title":"On the moment-transfer approach for random variables satisfying a one-sided distributional recurrence","volume":"16","author":"Chen","year":"2011","journal-title":"Electron. J. Probab."},{"key":"2026010107152412500_B20","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0025-5564(99)00060-7","article-title":"Distributions of cherries for two models of trees","volume":"164","author":"McKenzie","year":"2000","journal-title":"Math. Biosci."},{"key":"2026010107152412500_B21","volume-title":"Probability and measure","author":"Billingsley","year":"1995","edition":"3rd"},{"key":"2026010107152412500_B22","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/s00285-009-0275-6","article-title":"Limit theorems for patterns in phylogenetic trees","volume":"60","author":"Chang","year":"2010","journal-title":"J. Math. Biol."},{"key":"2026010107152412500_B23","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1051\/ita\/1989230303351","article-title":"A limiting distribution for Quicksort","volume":"23","author":"Regnier","year":"1989","journal-title":"RAIRO Inform. Th\u00e9orique Appl."},{"key":"2026010107152412500_B24","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1051\/ita\/1991250100851","article-title":"A limit theorem for 'quicksort'","volume":"25","author":"R\u00f6sler","year":"1991","journal-title":"RAIRO Theor. Informatics Appl."},{"key":"2026010107152412500_B25","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.mbs.2012.10.005","article-title":"A new balance index for phylogenetic trees","volume":"241","author":"Mir","year":"2013","journal-title":"Math. Biosci."},{"key":"2026010107152412500_B26","unstructured":"Chen\n              LA\n            \n          . 2015Probabilistic analysis of the total cophenetic index in phylogenetic trees. Masters thesis, National Chiao Tung Univesity (NCTU), Hsinchu."},{"key":"2026010107152412500_B27","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1214\/aoap\/1075828056","article-title":"A general limit theorem for recursive algorithms and combinatorial structures","volume":"14","author":"Neininger","year":"2004","journal-title":"Ann. Appl. Probab."},{"key":"2026010107152412500_B28","doi-asserted-by":"crossref","DOI":"10.1098\/rstb.2023.0307","article-title":"Labelled histories with multifurcation and simultaneity","volume":"380","author":"Dickey","year":"2025","journal-title":"Phil. Trans. R. Soc. B"},{"key":"2026010107152412500_B29","first-page":"1","volume-title":"Random discrete structures (IMA volumes in Mathematics and its Applications vol. 76)","author":"Aldous","year":"1996"},{"key":"2026010107152412500_B30","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1214\/ss\/998929474","article-title":"Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today","volume":"16","author":"Aldous","year":"2001","journal-title":"Stat. Sci."},{"key":"2026010107152412500_B31","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1080\/10635150600889625","article-title":"Which random processes describe the tree of life? A large-scale study of phylogenetic tree imbalance","volume":"55","author":"Blum","year":"2006","journal-title":"Syst. Biol."},{"key":"2026010107152412500_B32","unstructured":"Aldous\n              D\n            \n          . The critical beta-splitting random tree model II: overview and open problems. arXiv, 2303.02529. (doi:10.48550\/arXiv.2303.02529)"},{"key":"2026010107152412500_B33","unstructured":"Aldous\n              D\n            , PittelB. The critical beta-splitting random tree. arXiv, 2302.05066. (doi:10.48550\/arXiv.2302.05066)"},{"key":"2026010107152412500_B34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199601)8:1<1::AID-RSA1>3.0.CO;2-1","article-title":"On the distribution of binary search trees under the random permutation model","volume":"8","author":"Fill","year":"1996","journal-title":"Random Struc. Algor."},{"key":"2026010107152412500_B35","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1007\/s00285-019-01435-3","article-title":"Correlation between Shapley values of rooted phylogenetic trees under the beta-splitting model","volume":"80","author":"Fuchs","year":"2020","journal-title":"J. Math. Biol."},{"key":"2026010107152412500_B36","article-title":"Tree balance in phylogenetic models","volume":"380","author":"Kersting","journal-title":"Phil. Trans. R. Soc. B"},{"key":"2026010107152412500_B37","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic combinatorics","author":"Flajolet","year":"2009","edition":"1st"},{"key":"2026010107152412500_B38","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/S0196-6774(02)00293-6","article-title":"Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model","volume":"46","author":"Chen","year":"2003","journal-title":"J. Algor."},{"key":"2026010107152412500_B39","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1002\/rsa.10005","article-title":"Phase changes in random m-ary search trees and generalized quicksort","volume":"19","author":"Chern","year":"2001","journal-title":"Random Struct. Algor."},{"key":"2026010107152412500_B40","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1002\/rsa.20039","article-title":"Transfer theorems and asymptotic distributional results for m-ary search trees","volume":"26","author":"Fill","year":"2005","journal-title":"Random Struct. Algor."},{"key":"2026010107152412500_B41","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s00453-006-0109-5","article-title":"Profiles of random trees: limit theorems for random recursive trees and binary search trees","volume":"46","author":"Fuchs","year":"2006","journal-title":"Algorithmica"}],"container-title":["Philosophical Transactions B"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/royalsocietypublishing.org\/doi\/pdf\/10.1098\/rstb.2023.0304","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/royalsocietypublishing.org\/doi\/full-xml\/10.1098\/rstb.2023.0304","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/royalsocietypublishing.org\/rstb\/article-pdf\/doi\/10.1098\/rstb.2023.0304\/1282911\/rstb.2023.0304.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/royalsocietypublishing.org\/rstb\/article-pdf\/doi\/10.1098\/rstb.2023.0304\/1282911\/rstb.2023.0304.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T12:15:41Z","timestamp":1767269741000},"score":1,"resource":{"primary":{"URL":"https:\/\/royalsocietypublishing.org\/rstb\/article\/380\/1919\/20230304\/109671\/Shape-parameters-of-evolutionary-trees-in"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,13]]},"references-count":41,"journal-issue":{"issue":"1919","published-online":{"date-parts":[[2025,2,20]]},"published-print":{"date-parts":[[2025,2,13]]}},"URL":"https:\/\/doi.org\/10.1098\/rstb.2023.0304","relation":{},"ISSN":["1471-2970","0962-8436"],"issn-type":[{"value":"1471-2970","type":"electronic"},{"value":"0962-8436","type":"print"}],"subject":[],"published":{"date-parts":[[2025,2,13]]},"assertion":[{"value":"2024-04-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-02","order":1,"name":"revised","label":"Revised","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"20230304"}}