{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:47:12Z","timestamp":1767138432425,"version":"build-2238731810"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031221040","type":"print"},{"value":"9783031221057","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Gene trees inferred from alignments of molecular sequences are usually unrooted. Since the root of a gene tree is often the desired property, one of the most classical problems in computational biology is gene tree rooting, where the goal is to infer the most credible rooting edge in an unrooted gene tree. One way to solve it is to apply unrooted reconciliation, where the rooting edge is postulated based on a given split of a rooted species tree. Here, we address a novel variant of the rooting problem, where the gene tree root is inferred using a given phylogenetic network of the species present in the gene tree. One can apply unrooted reconciliation to obtain the best rooting, where the unrooted gene tree is jointly reconciled with a set of splits inferred from the given network. Natural candidates are splits induced by display trees of\u00a0the network. However, such an approach is computationally prohibiting due to the exponential size of the set. Therefore, we propose a broader and easier-to-control set of splits based on the structural properties of the network. Next, we derive exact mathematical formulas for the rooting problem with the algorithm that runs in square time and space. We verify the algorithm\u2019s quality based on simulated gene trees and networks.<\/jats:p>","DOI":"10.1007\/978-3-031-22105-7_37","type":"book-chapter","created":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T21:36:12Z","timestamp":1672522572000},"page":"419-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Rooting Gene Trees via\u00a0Phylogenetic Networks"],"prefix":"10.1007","author":[{"given":"Jerzy","family":"Tiuryn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natalia","family":"Rutecka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"G\u00f3recki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"issue":"8","key":"37_CR1","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., Bapteste, E., et al.: Networks: expanding evolutionary thinking. Trends Genet. 29(8), 439\u2013441 (2013)","journal-title":"Trends Genet."},{"issue":"3","key":"37_CR2","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1016\/j.ympev.2009.11.016","volume":"54","author":"LM Boykin","year":"2010","unstructured":"Boykin, L.M., Kubatko, L.S., Lowrey, T.K.: Comparison of methods for rooting phylogenetic trees: a case study using Orcuttieae (Poaceae: Chloridoideae). Mol. Phylogenet. Evol. 54(3), 687\u2013700 (2010)","journal-title":"Mol. Phylogenet. Evol."},{"issue":"3\u20134","key":"37_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1089\/106652700750050871","volume":"7","author":"K Chen","year":"2000","unstructured":"Chen, K., Durand, D., Farach-Colton, M.: NOTUNG: a program for dating gene duplications and optimizing gene family trees. J. Comput. Biol. 7(3\u20134), 429\u2013447 (2000)","journal-title":"J. Comput. Biol."},{"issue":"951","key":"37_CR4","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1086\/282802","volume":"106","author":"JS Farris","year":"1972","unstructured":"Farris, J.S.: Estimating phylogenetic trees from distance matrices. Am. Nat. 106(951), 645\u2013668 (1972)","journal-title":"Am. Nat."},{"issue":"8","key":"37_CR5","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1093\/molbev\/msp098","volume":"26","author":"W Fletcher","year":"2009","unstructured":"Fletcher, W., Yang, Z.: Indelible: a flexible simulator of biological sequence evolution. Molecular Biology and Evolution 26(8), 1879\u20131888 (2009)","journal-title":"Molecular Biology and Evolution"},{"key":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/978-3-642-32241-9_45","volume-title":"Computing and Combinatorics","author":"P G\u00f3recki","year":"2012","unstructured":"G\u00f3recki, P., Eulenstein, O.: Deep coalescence reconciliation with unrooted gene trees: linear time algorithms. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 531\u2013542. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32241-9_45"},{"issue":"2","key":"37_CR7","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1109\/TCBB.2013.22","volume":"10","author":"P G\u00f3recki","year":"2013","unstructured":"G\u00f3recki, P., Eulenstein, O., Tiuryn, J.: Unrooted tree reconciliation: a unified approach. IEEE\/ACM Trans. Comput. Biol. Bioinform. 10(2), 522\u2013536 (2013)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"2","key":"37_CR8","doi-asserted-by":"publisher","first-page":"e116","DOI":"10.1093\/bioinformatics\/btl296","volume":"23","author":"P G\u00f3recki","year":"2007","unstructured":"G\u00f3recki, P., Tiuryn, J.: Inferring phylogeny from whole genomes. Bioinformatics 23(2), e116\u2013e122 (2007)","journal-title":"Bioinformatics"},{"issue":"4","key":"37_CR9","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1093\/sysbio\/syq026","volume":"52","author":"K Hartmann","year":"2010","unstructured":"Hartmann, K., Wong, D., Stadler, T.: Sampling trees from evolutionary models. Syst. Biol. 52(4), 465\u2013476 (2010)","journal-title":"Syst. Biol."},{"key":"37_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974076","volume-title":"Phylogenetic Networks: Concepts Algorithms and Applications","author":"DH Huson","year":"2010","unstructured":"Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts Algorithms and Applications. Cambridge University Press, New York (2010)"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Kinene, T., Wainaina, J., Maina, S., Boykin, L.: Rooting trees, methods for. In: Encyclopedia of Evolutionary Biology, pp. 489\u2013493. Elsevier (2016)","DOI":"10.1016\/B978-0-12-800049-6.00215-8"},{"issue":"12","key":"37_CR12","doi-asserted-by":"publisher","first-page":"2669","DOI":"10.1093\/molbev\/msm193","volume":"24","author":"T Lepage","year":"2007","unstructured":"Lepage, T., Bryant, D., Philippe, H., Lartillot, N.: A general comparison of relaxed molecular clock models. Mol. Biol. Evol. 24(12), 2669\u20132680 (2007)","journal-title":"Mol. Biol. Evol."},{"issue":"1","key":"37_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1093\/sysbio\/33.1.83","volume":"33","author":"WP Maddison","year":"1984","unstructured":"Maddison, W.P., Donoghue, M.J., Maddison, D.R.: Outgroup analysis and parsimony. Syst. Biol. 33(1), 83\u2013103 (1984)","journal-title":"Syst. Biol."},{"issue":"8","key":"37_CR14","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0182238","volume":"12","author":"U Mai","year":"2017","unstructured":"Mai, U., Sayyari, E., Mirarab, S.: Minimum variance rooting of phylogenetic trees and implications for species tree reconstruction. PLoS ONE 12(8), e0182238 (2017)","journal-title":"PLoS ONE"},{"issue":"2","key":"37_CR15","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1093\/sysbio\/syv082","volume":"65","author":"D Mallo","year":"2015","unstructured":"Mallo, D., De Oliveira Martins, L., Posada, D.: SimPhy: phylogenomic simulation of gene, locus, and species trees. Syst. Biol. 65(2), 334\u2013344 (2015)","journal-title":"Syst. Biol."},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Molloy, E.K., Warnow, T.: FastMulRFS: fast and accurate species tree estimation under generic gene duplication and loss models. Bioinformatics 36(Supplement_1), i57\u2013i65 (2020)","DOI":"10.1093\/bioinformatics\/btaa444"},{"issue":"3","key":"37_CR17","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1109\/TCBB.2017.2788888","volume":"16","author":"A Mykowiecka","year":"2019","unstructured":"Mykowiecka, A., G\u00f3recki, P.: Credibility of evolutionary events in gene trees. IEEE\/ACM Trans. Comput. Biol. Bioinform. 16(3), 713\u2013726 (2019)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"9","key":"37_CR18","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1093\/bioinformatics\/14.9.819","volume":"14","author":"RD Page","year":"1998","unstructured":"Page, R.D.: GeneTree: comparing gene and species phylogenies using reconciled trees. Bioinformatics 14(9), 819\u2013820 (1998)","journal-title":"Bioinformatics"},{"issue":"4","key":"37_CR19","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1101\/gr.123901.111","volume":"22","author":"MD Rasmussen","year":"2012","unstructured":"Rasmussen, M.D., Kellis, M.: Unified modeling of gene duplication, loss, and coalescence using a locus tree. Genome Res. 22(4), 755\u2013765 (2012)","journal-title":"Genome Res."},{"key":"37_CR20","unstructured":"Steel, M.: Phylogeny. Society for Industrial and Applied Mathematics (2016)"},{"issue":"1","key":"37_CR21","first-page":"1","volume":"1","author":"FDK Tria","year":"2017","unstructured":"Tria, F.D.K., Landan, G., Dagan, T.: Phylogenetic rooting using minimal ancestor deviation. Nat. Ecol. Evol. 1(1), 1\u20137 (2017)","journal-title":"Nat. Ecol. Evol."},{"issue":"5","key":"37_CR22","doi-asserted-by":"publisher","first-page":"e0232950","DOI":"10.1371\/journal.pone.0232950","volume":"15","author":"T Wade","year":"2020","unstructured":"Wade, T., Rangel, L.T., Kundu, S., Fournier, G.P., Bansal, M.S.: Assessing the accuracy of phylogenetic rooting methods on prokaryotic gene families. PLoS ONE 15(5), e0232950 (2020)","journal-title":"PLoS ONE"},{"issue":"1","key":"37_CR23","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1186\/s13015-022-00218-8","volume":"17","author":"M Wawerka","year":"2022","unstructured":"Wawerka, M., Dabkowski, D., Rutecka, N., Mykowiecka, A., G\u00f3recki, P.: Embedding gene trees into phylogenetic networks by conflict resolution algorithms. Algorithms Mol. Biol. 17(1), 11 (2022)","journal-title":"Algorithms Mol. Biol."},{"key":"37_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-642-04241-6_31","volume-title":"Algorithms in Bioinformatics","author":"TJ Wheeler","year":"2009","unstructured":"Wheeler, T.J.: Large-scale neighbor-joining with NINJA. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol. 5724, pp. 375\u2013389. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04241-6_31"},{"issue":"1678","key":"37_CR25","doi-asserted-by":"publisher","first-page":"20140336","DOI":"10.1098\/rstb.2014.0336","volume":"370","author":"TA Williams","year":"2015","unstructured":"Williams, T.A., Heaps, S.E., Cherlin, S., Nye, T.M., Boys, R.J., Embley, T.M.: New substitution models for rooting phylogenetic trees. Philos. Trans. R. Soc. B: Biol. Sci. 370(1678), 20140336 (2015)","journal-title":"Philos. Trans. R. Soc. B: Biol. Sci."}],"updated-by":[{"DOI":"10.1007\/978-3-031-22105-7_52","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000}}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22105-7_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T18:06:50Z","timestamp":1680199610000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22105-7_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031221040","9783031221057"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22105-7_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"1 January 2023","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"A correction has been published.","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shenzhen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"101","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}