{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T12:16:36Z","timestamp":1754396196811,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2019\/33\/B\/ST6\/00737","2017\/27\/B\/ST6\/02720"],"award-info":[{"award-number":["2019\/33\/B\/ST6\/00737","2017\/27\/B\/ST6\/02720"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Gene trees inferred from molecular sequence alignments are typically unrooted, and determining the most credible rooting edge is a classical problem in computational biology. One approach to solve this problem is unrooted reconciliation, where the rooting edge is postulated based on the split of the root from a given species tree. In this paper, we propose a novel variant of the gene tree rooting problem, where the gene tree root is inferred using a phylogenetic network of the species present in the gene tree. To obtain the best rooting, unrooted reconciliation can be applied, where the unrooted gene tree is jointly reconciled with a set of splits inferred from the network. However, the exponential size of the set induced by display trees of the network makes this approach computationally prohibitive. To address this, we propose a broader and easier-to-control set of splits based on the structural properties of the network. We then derive exact mathematical formulas for the rooting problem and propose two general rooting algorithms to handle cases where the input network does not meet the initial requirements. Our experimental study based on simulated gene trees and networks demonstrates that our algorithms infer gene tree rootings correctly or with a small error in most cases.\n<\/jats:p>","DOI":"10.1007\/s10878-024-01181-3","type":"journal-article","created":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T13:01:51Z","timestamp":1717246911000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Phylogenetic network-assisted rooting of unrooted gene trees"],"prefix":"10.1007","volume":"47","author":[{"given":"Jerzy","family":"Tiuryn","sequence":"first","affiliation":[]},{"given":"Natalia","family":"Rutecka","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2045-5892","authenticated-orcid":false,"given":"Pawe\u0142","family":"G\u00f3recki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,1]]},"reference":[{"issue":"8","key":"1181_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, van Iersel L, Janke A, Kelchner S, Kelk S, McInerney JO, Morrison DA, Nakhleh L, Steel M, Stougie L, Whitfield J (2013) Networks: expanding evolutionary thinking. Trends Genet 29(8):439\u2013441","journal-title":"Trends Genet"},{"issue":"3","key":"1181_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 LM, Kubatko LS, Lowrey TK (2010) Comparison of methods for rooting phylogenetic trees: a case study using Orcuttieae (Poaceae: Chloridoideae). Mol Phylogenet Evol 54(3):687\u2013700","journal-title":"Mol Phylogenet Evol"},{"issue":"3\u20134","key":"1181_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 (2000) NOTUNG: a program for dating gene duplications and optimizing gene family trees. J Comput Biol 7(3\u20134):429\u2013447","journal-title":"J Comput Biol"},{"issue":"951","key":"1181_CR4","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1086\/282802","volume":"106","author":"JS Farris","year":"1972","unstructured":"Farris JS (1972) Estimating phylogenetic trees from distance matrices. Am Nat 106(951):645\u2013668","journal-title":"Am Nat"},{"issue":"8","key":"1181_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 (2009) Indelible: a flexible simulator of biological sequence evolution. Mol Biol Evol 26(8):1879\u20131888","journal-title":"Mol Biol Evol"},{"issue":"1\u20133","key":"1181_CR6","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.tcs.2006.05.019","volume":"359","author":"P G\u00f3recki","year":"2006","unstructured":"G\u00f3recki P, Tiuryn J (2006) DLS-trees: a model of evolutionary scenarios. Theoret Comput Sci 359(1\u20133):378\u2013399","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"1181_CR7","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 (2007) Inferring phylogeny from whole genomes. Bioinformatics 23(2):e116\u2013e122","journal-title":"Bioinformatics"},{"key":"1181_CR8","doi-asserted-by":"crossref","unstructured":"G\u00f3recki P, Eulenstein O (2012) Deep coalescence reconciliation with unrooted gene trees: linear time algorithms. In: International computing and combinatorics conference, pp 531\u2013542. Springer","DOI":"10.1007\/978-3-642-32241-9_45"},{"issue":"2","key":"1181_CR9","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 (2013) Unrooted tree reconciliation: a unified approach. IEEE\/ACM Trans Comput Biol Bioinf 10(2):522\u2013536","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"4","key":"1181_CR10","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 (2010) Sampling trees from evolutionary models. Syst Biol 52(4):465\u2013476","journal-title":"Syst Biol"},{"key":"1181_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974076","volume-title":"Phylogenetic networks: concepts algorithms and applications","author":"DH Huson","year":"2010","unstructured":"Huson DH, Rupp R, Scornavacca C (2010) Phylogenetic networks: concepts algorithms and applications. Cambridge University Press, New York"},{"key":"1181_CR12","doi-asserted-by":"crossref","unstructured":"Kinene T, Wainaina J, Maina S, Boykin L (2016) Rooting trees, methods for. In: Encyclopedia of evolutionary biology, pp 489\u2013493. Elsevier, Amsterdam","DOI":"10.1016\/B978-0-12-800049-6.00215-8"},{"issue":"S9","key":"1181_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1186\/s12859-018-2269-0","volume":"19","author":"S Kundu","year":"2018","unstructured":"Kundu S, Bansal MS (2018) On the impact of uncertain gene tree rooting on duplication-transfer-loss reconciliation. BMC Bioinf 19(S9):21\u201331. https:\/\/doi.org\/10.1186\/s12859-018-2269-0","journal-title":"BMC Bioinf"},{"issue":"12","key":"1181_CR14","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 (2007) A general comparison of relaxed molecular clock models. Mol Biol Evol 24(12):2669\u20132680","journal-title":"Mol Biol Evol"},{"issue":"1","key":"1181_CR15","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1093\/sysbio\/33.1.83","volume":"33","author":"WP Maddison","year":"1984","unstructured":"Maddison WP, Donoghue MJ, Maddison DR (1984) Outgroup analysis and parsimony. Syst Biol 33(1):83\u2013103","journal-title":"Syst Biol"},{"issue":"8","key":"1181_CR16","doi-asserted-by":"publisher","first-page":"e0182238","DOI":"10.1371\/journal.pone.0182238","volume":"12","author":"U Mai","year":"2017","unstructured":"Mai U, Sayyari E, Mirarab S (2017) Minimum variance rooting of phylogenetic trees and implications for species tree reconstruction. PLoS ONE 12(8):e0182238","journal-title":"PLoS ONE"},{"issue":"2","key":"1181_CR17","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 (2015) Simphy: phylogenomic simulation of gene, locus, and species trees. Syst Biol 65(2):334\u2013344","journal-title":"Syst Biol"},{"key":"1181_CR18","doi-asserted-by":"publisher","first-page":"i57","DOI":"10.1093\/bioinformatics\/btaa444","volume":"36","author":"EK Molloy","year":"2020","unstructured":"Molloy EK, Warnow T (2020) Fastmulrfs: fast and accurate species tree estimation under generic gene duplication and loss models. Bioinformatics 36:i57\u2013i65","journal-title":"Bioinformatics"},{"issue":"3","key":"1181_CR19","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 (2019) Credibility of evolutionary events in gene trees. IEEE\/ACM Trans Comput Biol Bioinf 16(3):713\u2013726","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"9","key":"1181_CR20","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1093\/bioinformatics\/14.9.819","volume":"14","author":"RD Page","year":"1998","unstructured":"Page RD (1998) Genetree: comparing gene and species phylogenies using reconciled trees. Bioinformatics 14(9):819\u2013820","journal-title":"Bioinformatics"},{"issue":"4","key":"1181_CR21","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1101\/gr.123901.111","volume":"22","author":"MD Rasmussen","year":"2012","unstructured":"Rasmussen MD, Kellis M (2012) Unified modeling of gene duplication, loss, and coalescence using a locus tree. Genome Res 22(4):755\u2013765","journal-title":"Genome Res"},{"key":"1181_CR22","doi-asserted-by":"crossref","unstructured":"Steel M (2016) Phylogeny. Soc Ind Appl Math","DOI":"10.1137\/1.9781611974485"},{"key":"1181_CR23","doi-asserted-by":"publisher","unstructured":"Tiuryn J, Rutecka N, G\u00f3recki P (2022) Rooting gene trees via\u00a0phylogenetic networks. In: Lecture notes in computer science, pp 419\u2013431. Springer International Publishing, Berlin. https:\/\/doi.org\/10.1007\/978-3-031-22105-7_37","DOI":"10.1007\/978-3-031-22105-7_37"},{"issue":"1","key":"1181_CR24","first-page":"1","volume":"1","author":"FDK Tria","year":"2017","unstructured":"Tria FDK, Landan G, Dagan T (2017) Phylogenetic rooting using minimal ancestor deviation. Nat Ecol Evol 1(1):1\u20137","journal-title":"Nat Ecol Evol"},{"issue":"5","key":"1181_CR25","doi-asserted-by":"publisher","first-page":"e0232950","DOI":"10.1371\/journal.pone.0232950","volume":"15","author":"T Wade","year":"2020","unstructured":"Wade T, Rangel LT, Kundu S, Fournier GP, Bansal MS (2020) Assessing the accuracy of phylogenetic rooting methods on prokaryotic gene families. PLoS ONE 15(5):e0232950","journal-title":"PLoS ONE"},{"issue":"1","key":"1181_CR26","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 (2022) Embedding gene trees into phylogenetic networks by conflict resolution algorithms. Algorithms Mol Biol 17(1):11","journal-title":"Algorithms Mol Biol"},{"key":"1181_CR27","doi-asserted-by":"crossref","unstructured":"Wheeler TJ (2009) Large-Scale Neighbor-Joining with NINJA. In: Algorithms in bioinformatics: 9th international workshop, WABI 2009","DOI":"10.1007\/978-3-642-04241-6_31"},{"issue":"1678","key":"1181_CR28","doi-asserted-by":"publisher","first-page":"20140336","DOI":"10.1098\/rstb.2014.0336","volume":"370","author":"TA Williams","year":"2015","unstructured":"Williams TA, Heaps SE, Cherlin S, Nye TM, Boys RJ, Embley TM (2015) New substitution models for rooting phylogenetic trees. Philos Trans Royal Soc B Biol Sci 370(1678):20140336","journal-title":"Philos Trans Royal Soc B Biol Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01181-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01181-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01181-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T14:41:14Z","timestamp":1721659274000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01181-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,1]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1181"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01181-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,6,1]]},"assertion":[{"value":"6 May 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"82"}}