{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T04:31:38Z","timestamp":1775017898018,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NWO","award":["639.072.602"],"award-info":[{"award-number":["639.072.602"]}]},{"name":"NWO","award":["NETWORKS"],"award-info":[{"award-number":["NETWORKS"]}]},{"name":"NWO","award":["639.072.603"],"award-info":[{"award-number":["639.072.603"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"abstract":"Abstract<\/jats:title>We study the problem of finding a temporal hybridization network containing at most k<\/jats:italic> reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m<\/jats:italic> binary trees with n<\/jats:italic> leaves each with a running time of $$O(5^k\\cdot n\\cdot m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 5<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n n<\/mml:mi>\n \u00b7<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also present the concept of temporal distance<\/jats:italic>, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most d<\/jats:italic> and at most k<\/jats:italic> reticulations in $$O((8k)^d5^ k\\cdot k\\cdot n\\cdot m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n (<\/mml:mo>\n 8<\/mml:mn>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n \n 5<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n k<\/mml:mi>\n \u00b7<\/mml:mo>\n n<\/mml:mi>\n \u00b7<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. Lastly, we introduce an $$O(6^kk!\\cdot k\\cdot n^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 6<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n k<\/mml:mi>\n !<\/mml:mo>\n \u00b7<\/mml:mo>\n k<\/mml:mi>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithm for computing a temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.<\/jats:p>","DOI":"10.1007\/s00453-022-00946-8","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T18:22:13Z","timestamp":1648232533000},"page":"2050-2087","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["New FPT Algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees"],"prefix":"10.1007","volume":"84","author":[{"given":"Sander","family":"Borst","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7142-4706","authenticated-orcid":false,"given":"Leo","family":"van Iersel","sequence":"additional","affiliation":[]},{"given":"Mark","family":"Jones","sequence":"additional","affiliation":[]},{"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,25]]},"reference":[{"issue":"2","key":"946_CR1","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1002\/bies.201500149","volume":"38","author":"J Mallet","year":"2016","unstructured":"Mallet, J., Besansky, N., Hahn, M.W.: How reticulated are species? BioEssays 38(2), 140\u2013149 (2016). https:\/\/doi.org\/10.1002\/bies.201500149","journal-title":"BioEssays"},{"issue":"8","key":"946_CR2","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1038\/nrg3962","volume":"16","author":"SM Soucy","year":"2015","unstructured":"Soucy, S.M., Huang, J., Gogarten, J.P.: Horizontal gene transfer: building the web of life. Nat Rev Genet 16(8), 472\u2013482 (2015). https:\/\/doi.org\/10.1038\/nrg3962","journal-title":"Nat Rev Genet"},{"issue":"8","key":"946_CR3","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.tig.2013.05.007","volume":"29","author":"E Bapteste","year":"2013","unstructured":"Bapteste, E., van Iersel, L., Janke, A., Kelchner, S., Kelk, S., McInerney, J.O., Morrison, D.A., Nakhleh, L., Steel, M., Stougie, L., Whitfield, J.: Networks: expanding evolutionary thinking. Trends Genet. 29(8), 439\u2013441 (2013). https:\/\/doi.org\/10.1016\/j.tig.2013.05.007","journal-title":"Trends Genet."},{"issue":"8","key":"946_CR4","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1016\/j.dam.2006.08.008","volume":"155","author":"M Bordewich","year":"2007","unstructured":"Bordewich, M., Semple, C.: Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Appl. Math. 155(8), 914\u2013928 (2007). https:\/\/doi.org\/10.1016\/j.dam.2006.08.008","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"946_CR5","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1016\/j.jcss.2016.03.006","volume":"82","author":"L van Iersel","year":"2016","unstructured":"van Iersel, L., Kelk, S., Scornavacca, C.: Kernelizations for the hybridization number problem on multiple nonbinary trees. J. Comput. Syst. Sci. 82(6), 1075\u20131089 (2016). https:\/\/doi.org\/10.1016\/j.jcss.2016.03.006","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"946_CR6","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1109\/tcbb.2007.1019","volume":"4","author":"M Bordewich","year":"2007","unstructured":"Bordewich, M., Semple, C.: Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable. IEEE\/ACM Trans. Comput. Biol. Bioinformatics 4(3), 458\u2013466 (2007). https:\/\/doi.org\/10.1109\/tcbb.2007.1019","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"946_CR7","unstructured":"Cardona, G., Rossello, F., Valiente, G.: Comparison of tree-child phylogenetic networks. arXiv:0708.3499 [cs, q-bio] (2007). http:\/\/arxiv.org\/abs\/0708.3499. ArXiv: 0708.3499"},{"key":"946_CR8","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.aam.2019.01.004","volume":"105","author":"S Linz","year":"2019","unstructured":"Linz, S., Semple, C.: Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies. Adv. Appl. Math. 105, 102\u2013129 (2019). https:\/\/doi.org\/10.1016\/j.aam.2019.01.004","journal-title":"Adv. Appl. Math."},{"key":"946_CR9","unstructured":"van Iersel, L., Janssen, R., Jones, M., Murakami, Y., Zeh, N.: A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees. arXiv:1907.08474 [cs, math, q-bio] (2019). http:\/\/arxiv.org\/abs\/1907.08474. ArXiv: 1907.08474"},{"issue":"10","key":"946_CR10","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1007\/s11538-013-9874-x","volume":"75","author":"PJ Humphries","year":"2013","unstructured":"Humphries, P.J., Linz, S., Semple, C.: Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies. Bull. Math. Biol. 75(10), 1879\u20131890 (2013). https:\/\/doi.org\/10.1007\/s11538-013-9874-x","journal-title":"Bull. Math. Biol."},{"issue":"7\u20138","key":"946_CR11","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1016\/j.dam.2012.11.022","volume":"161","author":"PJ Humphries","year":"2013","unstructured":"Humphries, P.J., Linz, S., Semple, C.: On the complexity of computing the temporal hybridization number for two phylogenies. Discrete Appl. Math. 161(7\u20138), 871\u2013880 (2013). https:\/\/doi.org\/10.1016\/j.dam.2012.11.022","journal-title":"Discrete Appl. Math."},{"key":"946_CR12","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.dam.2019.01.031","volume":"260","author":"J D\u00f6cker","year":"2019","unstructured":"D\u00f6cker, J., van Iersel, L., Kelk, S., Linz, S.: Deciding the existence of a cherry-picking sequence is hard on two trees. Discrete Appl. Math. 260, 131\u2013143 (2019). https:\/\/doi.org\/10.1016\/j.dam.2019.01.031","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"946_CR13","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1109\/TCBB.2008.86","volume":"6","author":"S Linz","year":"2009","unstructured":"Linz, S., Semple, C.: Hybridization in nonbinary trees. IEEE\/ACM Trans. Comput. Biol. Bioinformatics 6(1), 30\u201345 (2009). https:\/\/doi.org\/10.1109\/TCBB.2008.86","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"issue":"1","key":"946_CR14","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/TCBB.2012.134","volume":"10","author":"T Piovesan","year":"2013","unstructured":"Piovesan, T., Kelk, S.M.: A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees. IEEE\/ACM Trans. Comput. Biol. Bioinformatics 10(1), 18\u201325 (2013). https:\/\/doi.org\/10.1109\/TCBB.2012.134","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"946_CR15","doi-asserted-by":"publisher","unstructured":"Borst, S.: Temporal hybridization number algorithm implementations (2020). https:\/\/doi.org\/10.5281\/zenodo.3601812. https:\/\/github.com\/mathcals\/temporal_hybridization_number","DOI":"10.5281\/zenodo.3601812"},{"issue":"3","key":"946_CR16","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s00026-011-0108-3","volume":"15","author":"S Linz","year":"2011","unstructured":"Linz, S., Semple, C.: A cluster reduction for computing the subtree distance between phylogenies. Ann. Combin. 15(3), 465\u2013484 (2011). https:\/\/doi.org\/10.1007\/s00026-011-0108-3","journal-title":"Ann. Combin."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00946-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00946-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00946-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T11:06:17Z","timestamp":1655982377000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00946-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,25]]},"references-count":16,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["946"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00946-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,25]]},"assertion":[{"value":"29 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}