{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:14:19Z","timestamp":1760238859276,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,9,8]],"date-time":"2020-09-08T00:00:00Z","timestamp":1599523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100005357","name":"Agent\u00fara na Podporu V\u00fdskumu a V\u00fdvoja","doi-asserted-by":"publisher","award":["APVV-18-0239"],"award-info":[{"award-number":["APVV-18-0239"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006109","name":"Vedeck\u00e1 Grantov\u00e1 Agent\u00fara M\u0160VVa\u0160 SR a SAV","doi-asserted-by":"publisher","award":["1\/0463\/20","1\/0601\/20","1\/0458\/18"],"award-info":[{"award-number":["1\/0463\/20","1\/0601\/20","1\/0458\/18"]}],"id":[{"id":"10.13039\/501100006109","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the reconciliation problem, we are given two phylogenetic trees. A species tree represents the evolutionary history of a group of species, and a gene tree represents the history of a family of related genes within these species. A reconciliation maps nodes of the gene tree to the corresponding points of the species tree, and thus helps to interpret the gene family history. In this paper, we study the case when both trees are unrooted and their edge lengths are known exactly. The goal is to root them and to find a reconciliation that agrees with the edge lengths. We show a linear-time algorithm for finding the set of all possible root locations, which is a significant improvement compared to the previous O(N3logN) algorithm.<\/jats:p>","DOI":"10.3390\/a13090225","type":"journal-article","created":{"date-parts":[[2020,9,8]],"date-time":"2020-09-08T09:03:48Z","timestamp":1599555828000},"page":"225","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9483-1766","authenticated-orcid":false,"given":"Bro\u0148a","family":"Brejov\u00e1","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynsk\u00e1 dolina, 842 48 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1121-1009","authenticated-orcid":false,"given":"Rastislav","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynsk\u00e1 dolina, 842 48 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1093\/sysbio\/28.2.132","article-title":"Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences","volume":"28","author":"Goodman","year":"1979","journal-title":"Syst. Biol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"14254","DOI":"10.1073\/pnas.0805217105","article-title":"The infinite sites model of genome evolution","volume":"105","author":"Ma","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1089\/cmb.2008.0069","article-title":"DUPCAR: Reconstructing contiguous ancestral regions with duplications","volume":"15","author":"Ma","year":"2008","journal-title":"J. Comput. Biol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1186\/s13015-017-0108-x","article-title":"Isometric gene tree reconciliation revisited","volume":"12","author":"Gafurov","year":"2017","journal-title":"Algorithms Mol. Biol."},{"key":"ref_5","unstructured":"Felsenstein, J. (2004). Inferring Phylogenies, Sinauer Associates."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1093\/bib\/bbr045","article-title":"Models, algorithms and programs for phylogeny reconciliation","volume":"12","author":"Doyon","year":"2011","journal-title":"Brief. Bioinform."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1089\/cmb.1997.4.177","article-title":"On a Mirkin-Muchnik-Smith conjecture for comparing molecular phylogenies","volume":"4","author":"Zhang","year":"1997","journal-title":"J. Comput. Biol."},{"key":"ref_8","unstructured":"Eulenstein, O. (1997). A Linear Time Algorithm for Tree Mapping, GMD-Forschungszentrum Informationstechnik."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"e116","DOI":"10.1093\/bioinformatics\/btl296","article-title":"Inferring phylogeny from whole genomes","volume":"23","author":"Tiuryn","year":"2007","journal-title":"Bioinformatics"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3267","DOI":"10.1093\/molbev\/msx259","article-title":"STRIDE: Species tree root inference from gene duplication events","volume":"34","author":"Emms","year":"2017","journal-title":"Mol. Biol. Evol."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1093\/sysbio\/syp046","article-title":"Probabilistic orthology analysis","volume":"58","author":"Sennblad","year":"2009","journal-title":"Syst. Biol."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"G\u00f3recki, P., Burleigh, G.J., and Eulenstein, O. (2011). Maximum likelihood models and algorithms for gene tree evolution with duplications and losses. BMC Bioinform., 12.","DOI":"10.1186\/1471-2105-12-S1-S15"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/TCBB.2011.64","article-title":"An efficient method for exploring the space of gene tree\/species tree reconciliations in a probabilistic framework","volume":"9","author":"Doyon","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_14","first-page":"93","article-title":"An efficient algorithm for gene\/species trees parsimonious reconciliation with losses, duplications and transfers","volume":"Volume 6398","author":"Doyon","year":"2010","journal-title":"Comparative Genomics (RECOMB-CG 2012)"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"i283","DOI":"10.1093\/bioinformatics\/bts225","article-title":"Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss","volume":"28","author":"Bansal","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","article-title":"Fast algorithms for finding nearest common ancestors","volume":"13","author":"Harel","year":"1984","journal-title":"SIAM J. Comput."},{"key":"ref_17","first-page":"88","article-title":"The LCA problem revisited","volume":"Volume 1776","author":"Bender","year":"2000","journal-title":"LATIN 2000: Theoretical Informatics"},{"key":"ref_18","first-page":"406","article-title":"The neighbor-joining method: A new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1109\/TCBB.2013.22","article-title":"Unrooted tree reconciliation: A unified approach","volume":"10","author":"Eulenstein","year":"2013","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/225\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:07:50Z","timestamp":1760177270000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,8]]},"references-count":19,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090225"],"URL":"https:\/\/doi.org\/10.3390\/a13090225","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,9,8]]}}}