{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T06:18:39Z","timestamp":1772173119327,"version":"3.50.1"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1010532","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000}}],"reference-count":25,"publisher":"Public Library of Science (PLoS)","issue":"9","license":[{"start":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T00:00:00Z","timestamp":1663200000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ERC starting grant","award":["757648"],"award-info":[{"award-number":["757648"]}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Extracting information on the selective and demographic past of populations that is contained in samples of genome sequences requires a description of the distribution of the underlying genealogies. Using the Laplace transform, this distribution can be generated with a simple recursive procedure, regardless of model complexity. Assuming an infinite-sites mutation model, the probability of observing specific configurations of linked variants within small haplotype blocks can be recovered from the Laplace transform of the joint distribution of branch lengths. However, the repeated differentiation required to compute these probabilities has proven to be a serious computational bottleneck in earlier implementations.<\/jats:p>\n                  <jats:p>\n                    Here, I show that the state space diagram can be turned into a computational graph, allowing efficient evaluation of the Laplace transform by means of a graph traversal algorithm. This general algorithm can, for example, be applied to tabulate the likelihoods of mutational configurations in non-recombining blocks. This work provides a crucial speed up for existing composite likelihood approaches that rely on the joint distribution of branch lengths to fit isolation with migration models and estimate the parameters of selective sweeps. The associated software is available as an open-source Python library,\n                    <jats:monospace>agemo<\/jats:monospace>\n                    .\n                  <\/jats:p>","DOI":"10.1371\/journal.pcbi.1010532","type":"journal-article","created":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T14:01:29Z","timestamp":1663250489000},"page":"e1010532","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":6,"title":["Graph-based algorithms for Laplace transformed coalescence time distributions"],"prefix":"10.1371","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8327-0142","authenticated-orcid":true,"given":"Gertjan","family":"Bisschop","sequence":"first","affiliation":[]}],"member":"340","published-online":{"date-parts":[[2022,9,15]]},"reference":[{"issue":"1","key":"pcbi.1010532.ref001","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1080\/0020739720030104","article-title":"On the use of generating functions and laplace transforms in applied probability theory","volume":"3","author":"L R\u00e5de","year":"1972","journal-title":"International Journal of Mathematical Education in Science and Technology"},{"issue":"3","key":"pcbi.1010532.ref002","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0304-4149(82)90011-4","article-title":"The coalescent","volume":"13","author":"JFC Kingman","year":"1982","journal-title":"Stochastic Processes and their Applications"},{"issue":"1","key":"pcbi.1010532.ref003","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1111\/j.1558-5646.1983.tb05528.x","article-title":"Testing the constant-rate neutral allele model with protein sequence data","volume":"37","author":"RR Hudson","year":"1983","journal-title":"Evolution"},{"issue":"2","key":"pcbi.1010532.ref004","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1093\/genetics\/105.2.437","article-title":"Evolutionary relationship of DNA sequences in finite populations","volume":"105","author":"F Tajima","year":"1983","journal-title":"Genetics"},{"issue":"3","key":"pcbi.1010532.ref005","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1534\/genetics.111.129569","article-title":"A general method for calculating likelihoods under the coalescent process","volume":"189","author":"K Lohse","year":"2011","journal-title":"Genetics"},{"issue":"22","key":"pcbi.1010532.ref006","doi-asserted-by":"crossref","first-page":"5566","DOI":"10.1111\/mec.12958","article-title":"Testing models of speciation from genome sequences: Divergence and asymmetric admixture in Island South-East Asian Sus species during the Plio-Pleistocene climatic fluctuations","volume":"23","author":"LAF Frantz","year":"2014","journal-title":"Molecular Ecology"},{"issue":"3","key":"pcbi.1010532.ref007","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1534\/genetics.115.179861","article-title":"Inferring bottlenecks from genome-wide samples of short sequence blocks","volume":"201","author":"L Bunnefeld","year":"2015","journal-title":"Genetics"},{"issue":"2","key":"pcbi.1010532.ref008","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1534\/genetics.115.183814","article-title":"Efficient strategies for calculating blockwise likelihoods under the coalescent","volume":"202","author":"K Lohse","year":"2016","journal-title":"Genetics"},{"issue":"2","key":"pcbi.1010532.ref009","doi-asserted-by":"crossref","DOI":"10.1093\/genetics\/iyab119","article-title":"Sweeps in time: Leveraging the joint distribution of branch lengths","volume":"219","author":"G Bisschop","year":"2021","journal-title":"Genetics"},{"key":"pcbi.1010532.ref010","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.tpb.2019.02.001","article-title":"Phase-type distributions in population genetics","volume":"127","author":"A Hobolth","year":"2019","journal-title":"Theoretical Population Biology"},{"key":"pcbi.1010532.ref011","article-title":"Graph-based algorithms for phase-type distributions","author":"T R\u00f8ikjer","year":"2022","journal-title":"bioRxiv preprint"},{"key":"pcbi.1010532.ref012","first-page":"1","article-title":"Automatic Differentiation in Machine Learning: a Survey","volume":"18","author":"A G\u00fcne\u015f","year":"2018","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"pcbi.1010532.ref013","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/tpbi.1997.1307","article-title":"A Markov chain model of coalescence with recombination","volume":"52","author":"KL Simonsen","year":"1997","journal-title":"Theoretical Population Biology"},{"issue":"2","key":"pcbi.1010532.ref014","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/146847.146924","article-title":"An Efficient Method for the Numerical Evaluation of Partial Derivatives of Arbitrary Order","volume":"18","author":"RD Neidinger","year":"1992","journal-title":"ACM Transactions on Mathematical Software (TOMS)"},{"key":"pcbi.1010532.ref015","doi-asserted-by":"crossref","unstructured":"Neidinger RD. Computing multivariable Taylor series to arbitrary order. In: Proceedings of the international conference on Applied programming languages\u2014APL \u201995. New York, New York, USA: ACM Press; 1995. p. 134\u2013144.","DOI":"10.1145\/206913.206988"},{"issue":"231","key":"pcbi.1010532.ref016","first-page":"1117","article-title":"Evaluating Higher Derivative Tensors by Forward Propagation of Univariate Taylor Series","volume":"69","author":"A Griewank","year":"2000","journal-title":"Source: Mathematics of Computation"},{"key":"pcbi.1010532.ref017","unstructured":"Bettencourt J, Johnson MJ, Duvenaud BD. Taylor-Mode Automatic Differentiation for Higher-Order Derivatives in JAX. In: Program Transformations for ML Workshop at NeurIPS 2019; 2019. Available from: https:\/\/openreview.net\/forum?id=SkxEF3FNPH."},{"key":"pcbi.1010532.ref018","unstructured":"Neidinger RD. Efficient recurrence relations for univariate and multivariate Taylor series coefficients. Conference Publications. 2013; p. 587\u2013596."},{"issue":"6","key":"pcbi.1010532.ref019","doi-asserted-by":"crossref","first-page":"1955","DOI":"10.1137\/030601818","article-title":"Accurate sum and dot product","volume":"26","author":"T Ogita","year":"2005","journal-title":"SIAM Journal on Scientific Computing"},{"key":"pcbi.1010532.ref020","doi-asserted-by":"crossref","unstructured":"Lam SK, Pitrou A, Seibert S. Numba. In: Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC\u2014LLVM \u201915. New York, New York, USA: ACM Press; 2015. p. 1\u20136. Available from: http:\/\/dl.acm.org\/citation.cfm?doid=2833157.2833162.","DOI":"10.1145\/2833157.2833162"},{"issue":"2","key":"pcbi.1010532.ref021","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1093\/genetics\/158.2.885","article-title":"Distinguishing migration from isolation: A Markov chain Monte Carlo approach","volume":"158","author":"R Nielsen","year":"2001","journal-title":"Genetics"},{"key":"pcbi.1010532.ref022","unstructured":"The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.5.0); 2005."},{"issue":"1","key":"pcbi.1010532.ref023","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1186\/s13059-018-1517-y","article-title":"ABLE: blockwise site frequency spectra for inferring complex population histories and recombination","volume":"19","author":"CR Beeravolu","year":"2018","journal-title":"Genome Biology"},{"issue":"3","key":"pcbi.1010532.ref024","doi-asserted-by":"crossref","DOI":"10.1093\/genetics\/iyab229","article-title":"Efficient ancestry and mutation simulation with msprime 1.0","volume":"220","author":"F Baumdicker","year":"2022","journal-title":"Genetics"},{"issue":"10","key":"pcbi.1010532.ref025","doi-asserted-by":"crossref","first-page":"1505","DOI":"10.1101\/gr.6409707","article-title":"A new approach to estimate parameters of speciation models with application to apes","volume":"17","author":"C Becquet","year":"2007","journal-title":"Genome Research"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1010532","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010532","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T13:42:44Z","timestamp":1664286164000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010532"}},"subtitle":[],"editor":[{"given":"Mark M.","family":"Tanaka","sequence":"first","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,9,15]]},"references-count":25,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,9,15]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1010532","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2022.05.20.492768","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,15]]}}}