{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:10:11Z","timestamp":1773274211176,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","funder":[{"DOI":"10.13039\/501100011958","name":"Danmarks Frie Forskningsfond","doi-asserted-by":"crossref","award":["DFF-1323-00247"],"award-info":[{"award-number":["DFF-1323-00247"]}],"id":[{"id":"10.13039\/501100011958","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100011958","name":"Danmarks Frie Forskningsfond","doi-asserted-by":"crossref","award":["DFF-7014-00041"],"award-info":[{"award-number":["DFF-7014-00041"]}],"id":[{"id":"10.13039\/501100011958","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1186\/s13015-018-0121-8","type":"journal-article","created":{"date-parts":[[2018,2,5]],"date-time":"2018-02-05T20:56:36Z","timestamp":1517864196000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Time-consistent reconciliation maps and forbidden time travel"],"prefix":"10.1186","volume":"13","author":[{"given":"Nikolai","family":"N\u00f8jgaard","sequence":"first","affiliation":[]},{"given":"Manuela","family":"Gei\u00df","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Merkle","sequence":"additional","affiliation":[]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[]},{"given":"Nicolas","family":"Wieseke","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Hellmuth","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,6]]},"reference":[{"key":"121_CR1","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1016\/j.jtbi.2010.05.031","volume":"265","author":"A Dress","year":"2010","unstructured":"Dress A, Moulton V, Steel M, Wu T. Species, clusters and the \u2018tree of life\u2019: a graph-theoretic perspective. J Theor Biol. 2010;265:535\u201342.","journal-title":"J Theor Biol"},{"key":"121_CR2","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0168-9525(00)02005-9","volume":"16","author":"WM Fitch","year":"2000","unstructured":"Fitch WM. Homology: a personal view on some of the problems. Trends Genet. 2000;16:227\u201331.","journal-title":"Trends Genet"},{"issue":"1","key":"121_CR3","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00285-016-1084-3","volume":"75","author":"M Hellmuth","year":"2016","unstructured":"Hellmuth M, Stadler PF, Wieseke N. The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree- representable systems of binary relations. J Math Biol. 2016;75(1):199\u2013237. https:\/\/doi.org\/10.1007\/s00285-016-1084-3 .","journal-title":"J Math Biol"},{"key":"121_CR4","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-319-41324-2_21","volume-title":"Evolutionary Biology: convergent evolution, evolution of complex traits, concepts and methods","author":"M Hellmuth","year":"2016","unstructured":"Hellmuth M, Wieseke N. From sequence data including orthologs, paralogs, and xenologs to gene and species trees. In: Pontarotti P, editor. Evolutionary Biology: convergent evolution, evolution of complex traits, concepts and methods. Cham: Springer; 2016. p. 373\u201392."},{"key":"121_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1006\/mpev.1996.0071","volume":"6","author":"R Guig\u00f3","year":"1996","unstructured":"Guig\u00f3 R, Muchnik I, Smith T. Reconstruction of ancient molecular phylogeny. Mol Phylogenet Evol. 1996;6:189\u2013213.","journal-title":"Mol Phylogenet Evol"},{"key":"121_CR6","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/S0169-5347(98)01438-4","volume":"13","author":"RDM Page","year":"1998","unstructured":"Page RDM, Charleston MA. Trees within trees: phylogeny and historical associations. Trends Ecol Evol. 1998;13:356\u20139.","journal-title":"Trends Ecol Evol"},{"key":"121_CR7","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1093\/bioinformatics\/17.9.821","volume":"17","author":"C Zmasek","year":"2001","unstructured":"Zmasek C, Eddy S. A simple algorithm to infer gene duplication and speciation events on a gene tree. Bioinformatics. 2001;17:821\u20138.","journal-title":"Bioinformatics"},{"key":"121_CR8","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1089\/cmb.2008.0092","volume":"15","author":"B Vernot","year":"2008","unstructured":"Vernot B, Stolzer M, Goldman A, Durand D. Reconciliation with non-binary species trees. J Comput Biol. 2008;15:981\u20131006. https:\/\/doi.org\/10.1089\/cmb.2008.0092 .","journal-title":"J Comput Biol"},{"issue":"7","key":"121_CR9","doi-asserted-by":"publisher","first-page":"2058","DOI":"10.1073\/pnas.1412770112","volume":"112","author":"M Hellmuth","year":"2015","unstructured":"Hellmuth M, Wieseke N, Lechner M, Lenhof H-P, Middendorf M, Stadler PF. Phylogenomics with paralogs. Proc Natl Acad Sci. 2015;112(7):2058\u201363. https:\/\/doi.org\/10.1073\/pnas.1412770112 .","journal-title":"Proc Natl Acad Sci"},{"key":"121_CR10","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1186\/1471-2105-9-518","volume":"9","author":"ACJ Roth","year":"2008","unstructured":"Roth ACJ, Gonnet GH, Dessimoz C. Algorithm of OMA for large-scale orthology inference. BMC Bioinf. 2008;9:518.","journal-title":"BMC Bioinf"},{"key":"121_CR11","doi-asserted-by":"publisher","first-page":"1000262","DOI":"10.1371\/journal.pcbi.1000262","volume":"5","author":"AM Altenhoff","year":"2009","unstructured":"Altenhoff AM, Dessimoz C. Phylogenetic and functional assessment of orthologs inference projects and methods. PLoS Comput Biol. 2009;5:1000262.","journal-title":"PLoS Comput Biol."},{"issue":"8","key":"121_CR12","doi-asserted-by":"publisher","first-page":"105015","DOI":"10.1371\/journal.pone.0105015","volume":"9","author":"M Lechner","year":"2014","unstructured":"Lechner M, Hernandez-Rosales M, Doerr D, Wieseke N, Th\u00e9venin A, Stoye J, Hartmann RK, Prohaska SJ, Stadler PF. Orthology detection combining clustering and synteny for very large datasets. PLoS ONE. 2014;9(8):105015.","journal-title":"PLoS ONE"},{"key":"121_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1038\/nmeth.3830","volume":"13","author":"AM Altenhoff","year":"2016","unstructured":"Altenhoff AM, Boeckmann B, Capella-Gutierrez S, Dalquen DA, DeLuca T, Forslund K, Huerta-Cepas J, Linard B, Pereira C, Pryszcz LP, Schreiber F, da Silva AS, Szklarczyk D, Train CM, Bork P, Lecompte O, von Mering C, Xenarios I, Sj\u00f6lander K, Jensen LJ, Martin MJ, Muffato M, Gabald\u00f3n T, Lewis SE, Thomas PD, Sonnhammer E, Dessimoz C. Standardized benchmarking in the quest for orthologs. Nat Methods. 2016;13:425\u201330.","journal-title":"Nat Methods"},{"issue":"1\u20132","key":"121_CR14","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00285-012-0525-x","volume":"66","author":"M Hellmuth","year":"2013","unstructured":"Hellmuth M, Hernandez-Rosales M, Huber KT, Moulton V, Stadler PF, Wieseke N. Orthology relations, symbolic ultrametrics, and cographs. J Math Biol. 2013;66(1\u20132):399\u2013420.","journal-title":"J Math Biol"},{"issue":"1","key":"121_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1186\/s13015-017-0114-z","volume":"12","author":"M Hellmuth","year":"2017","unstructured":"Hellmuth M. Biologically feasible gene trees, reconciliation maps and informative triples. Algorithms Mol Biol. 2017;12(1):23.","journal-title":"Algorithms Mol Biol"},{"issue":"Suppl 19","key":"121_CR16","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1186\/1471-2105-13-S19-S6","volume":"13","author":"M Hernandez-Rosales","year":"2012","unstructured":"Hernandez-Rosales M, Hellmuth M, Wieseke N, Huber KT, Moulton V, Stadler PF. From event-labeled gene trees to species trees. BMC Bioinf. 2012;13(Suppl 19):6.","journal-title":"BMC Bioinf"},{"issue":"5","key":"121_CR17","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1093\/bib\/bbr045","volume":"12","author":"J-P Doyon","year":"2011","unstructured":"Doyon J-P, Ranwez V, Daubin V, Berry V. Models, algorithms and programs for phylogeny reconciliation. Brief Bioinf. 2011;12(5):392.","journal-title":"Brief Bioinf"},{"key":"121_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.thbio.2005.01.003","volume":"4","author":"D Merkle","year":"2005","unstructured":"Merkle D, Middendorf M. Reconstruction of the cophylogenetic history of related phylogenetic trees with divergence timing information. Theor Biosci. 2005;4:277\u201399.","journal-title":"Theor Biosci"},{"issue":"2","key":"121_CR19","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0025-5564(97)10012-8","volume":"149","author":"MA Charleston","year":"1998","unstructured":"Charleston MA. Jungles: a new solution to the host\/parasite phylogeny reconciliation problem. Math Biosci. 1998;149(2):191\u2013223.","journal-title":"Math Biosci"},{"issue":"2","key":"121_CR20","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1109\/TCBB.2010.14","volume":"8","author":"A Tofigh","year":"2011","unstructured":"Tofigh A, Hallett M, Lagergren J. Simultaneous identification of duplications and lateral gene transfers. IEEE\/ACM Trans Comput Biol Bioinf. 2011;8(2):517\u201335.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"121_CR21","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/aima.1998.1743","volume":"138","author":"S B\u00f6cker","year":"1998","unstructured":"B\u00f6cker S, Dress AWM. Recovering symbolically dated, rooted trees from symbolic ultrametrics. Adv Math. 1998;138:105\u201325.","journal-title":"Adv Math"},{"key":"121_CR22","series-title":"Proceedings COCOON 2015","first-page":"609","volume-title":"On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions","author":"M Hellmuth","year":"2015","unstructured":"Hellmuth M, Wieseke N. On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions., Proceedings COCOON 2015Cham: Springer; 2015. p. 609\u201323."},{"key":"121_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-017-0111-7","author":"M Hellmuth","year":"2017","unstructured":"Hellmuth M, Wieseke N. On tree representations of relations and graphs: Symbolic ultrametrics and cograph edge decompositions. J Comb Optim. 2017; https:\/\/doi.org\/10.1007\/s10878-017-0111-7 .","journal-title":"J Comb Optim"},{"issue":"12","key":"121_CR24","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1093\/bioinformatics\/bts225","volume":"28","author":"MS Bansal","year":"2012","unstructured":"Bansal MS, Alm EJ, Kellis M. Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics. 2012;28(12):283\u201391.","journal-title":"Bioinformatics"},{"issue":"11","key":"121_CR25","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn AB. Topological sorting of large networks. Commun ACM. 1962;5(11):558\u201362.","journal-title":"Commun ACM"},{"issue":"1","key":"121_CR26","doi-asserted-by":"publisher","first-page":"53786","DOI":"10.1371\/journal.pone.0053786","volume":"8","author":"AM Altenhoff","year":"2013","unstructured":"Altenhoff AM, Gil M, Gonnet GH, Dessimoz C. Inferring hierarchical orthologous groups from orthologous gene pairs. PLoS ONE. 2013;8(1):53786.","journal-title":"PLoS ONE"},{"issue":"D1","key":"121_CR27","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1093\/nar\/gku1158","volume":"43","author":"AM Altenhoff","year":"2015","unstructured":"Altenhoff AM, et al. The OMA orthology database in 2015: function predictions, better plant support, synteny view and other improvements. Nucleic Acids Res. 2015;43(D1):240\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"S1","key":"121_CR28","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1093\/nar\/gkj123","volume":"34","author":"F Chen","year":"2006","unstructured":"Chen F, Mackey AJ, Stoeckert CJ, Roos DS. OrthoMCL-db: querying a comprehensive multi-species collection of ortholog groups. Nucleic Acids Res. 2006;34(S1):363\u20138.","journal-title":"Nucleic Acids Res"},{"key":"121_CR29","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1186\/1471-2105-12-124","volume":"12","author":"M Lechner","year":"2011","unstructured":"Lechner M, Findei\u00df S, Steiner L, Marz M, Stadler PF, Prohaska SJ. Proteinortho: detection of (co-)orthologs in large-scale analysis. BMC Bioinf. 2011;12:124.","journal-title":"BMC Bioinf"},{"issue":"suppl 1","key":"121_CR30","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1093\/nar\/gkp931","volume":"38","author":"G \u00d6stlund","year":"2010","unstructured":"\u00d6stlund G, Schmitt T, Forslund K, K\u00f6stler T, Messina DN, Roopra S, Frings O, Sonnhammer ELL. InParanoid 7: new algorithms and tools for eukaryotic orthology analysis. Nucleic Acids Res. 2010;38(suppl 1):196\u2013203.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"121_CR31","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1093\/nar\/28.1.33","volume":"28","author":"RL Tatusov","year":"2000","unstructured":"Tatusov RL, Galperin MY, Natale DA, Koonin EV. The COG database: a tool for genome-scale analysis of protein functions and evolution. Nucleic Acids Res. 2000;28(1):33\u20136.","journal-title":"Nucleic Acids Res"},{"issue":"10","key":"121_CR32","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1002\/bies.201100062","volume":"33","author":"K Trachana","year":"2011","unstructured":"Trachana K, Larsson TA, Powell S, Chen W-H, Doerks T, Muller J, Bork P. Orthology prediction methods: a quality assessment using curated protein families. BioEssays. 2011;33(10):769\u201380.","journal-title":"BioEssays"},{"key":"121_CR33","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1093\/nar\/gkm1000","volume":"36","author":"DL Wheeler","year":"2008","unstructured":"Wheeler DL, Barrett T, Benson DA, Bryant SH, Canese K, Chetvernin V, Church DM, Dicuccio M, Edgar R, Federhen S, Feolo M, Geer LY, Helmberg W, Kapustin Y, Khovayko O, Landsman D, Lipman DJ, Madden TL, Maglott DR, Miller V, Ostell J, Pruitt KD, Schuler GD, Shumway M, Sequeira E, Sherry ST, Sirotkin K, Souvorov A, Starchenko G, Tatusov RL, Tatusova TA, Wagner L, Yaschenko E. Database resources of the national center for biotechnology information. Nucleic Acids Res. 2008;36:13\u201321.","journal-title":"Nucleic Acids Res."},{"issue":"8","key":"121_CR34","doi-asserted-by":"publisher","first-page":"2072","DOI":"10.1128\/JB.184.8.2072-2080.2002","volume":"184","author":"GDP Clarke","year":"2002","unstructured":"Clarke GDP, Beiko RG, Ragan MA, Charlebois RL. Inferring genome trees by using a filter to eliminate phylogenetically discordant sequences and a distance matrix based on mean normalized BLASTP scores. J Bacteriol. 2002;184(8):2072\u201380.","journal-title":"J Bacteriol"},{"key":"121_CR35","doi-asserted-by":"crossref","unstructured":"Dessimoz C, Margadant D, Gonnet GH. DLIGHT\u2014lateral gene transfer detection using pairwise evolutionary distances in a statistical framework. In: Proceedings RECOMB 2008, pp. 315\u2013330. Springer, Berlin; 2008.","DOI":"10.1007\/978-3-540-78839-3_27"},{"issue":"3","key":"121_CR36","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1093\/genetics\/131.3.753","volume":"131","author":"JG Lawrence","year":"1992","unstructured":"Lawrence JG, Hartl DL. Inference of horizontal genetic transfer from molecular data: an approach using the bootstrap. Genetics. 1992;131(3):753\u201360.","journal-title":"Genetics"},{"issue":"8","key":"121_CR37","doi-asserted-by":"publisher","first-page":"4285","DOI":"10.1073\/pnas.96.8.4285","volume":"96","author":"M Pellegrini","year":"1999","unstructured":"Pellegrini M, Marcotte EM, Thompson MJ, Eisenberg D, Yeates TO. Assigning protein functions by comparative genome analysis: protein phylogenetic profiles. Proc Natl Acad Sci USA. 1999;96(8):4285\u20138.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"5","key":"121_CR38","doi-asserted-by":"publisher","first-page":"1004095","DOI":"10.1371\/journal.pcbi.1004095","volume":"11","author":"M Ravenhall","year":"2015","unstructured":"Ravenhall M, \u0160kunca N, Lassalle F, Dessimoz C. Inferring horizontal gene transfer. PLoS Comput Biol. 2015;11(5):1004095.","journal-title":"PLoS Comput Biol"},{"issue":"1","key":"121_CR39","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/s13015-017-0096-x","volume":"12","author":"R Dondi","year":"2017","unstructured":"Dondi R, Lafond M, El-Mabrouk N. Approximating the correction of weighted and unweighted orthology and paralogy relations. Algorithms Mol Biol. 2017;12(1):4.","journal-title":"Algorithms Mol Biol"},{"issue":"6","key":"121_CR40","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1186\/1471-2164-15-S6-S12","volume":"15","author":"M Lafond","year":"2014","unstructured":"Lafond M, El-Mabrouk N. Orthology and paralogy constraints: satisfiability and consistency. BMC Genom. 2014;15(6):12.","journal-title":"BMC Genom"},{"key":"121_CR41","doi-asserted-by":"crossref","unstructured":"Lafond M, El-Mabrouk N. Orthology relation and gene tree correction: complexity results. In: International workshop on algorithms in bioinformatics, Berlin: Springer; 2015. p. 66\u201379.","DOI":"10.1007\/978-3-662-48221-6_5"},{"key":"121_CR42","doi-asserted-by":"crossref","unstructured":"Dondi R, El-Mabrouk N, Lafond M. Correction of weighted orthology and paralogy relations-complexity and algorithmic results. In: International workshop on algorithms in bioinformatics, Berlin: Springer; 2016. p. 121\u201336.","DOI":"10.1007\/978-3-319-43681-4_10"},{"key":"121_CR43","doi-asserted-by":"crossref","unstructured":"Dondi R, Mauri G, Zoppis I. Orthology correction for gene tree reconstruction: Theoretical and experimental results. Procedia Computer Science. International Conference on Computational Science, ICCS 2017, 12-14 June 2017, Zurich, Switzerland. p. 1115\u201324.","DOI":"10.1016\/j.procs.2017.05.047"},{"issue":"1","key":"121_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-016-0067-7","volume":"11","author":"M Lafond","year":"2016","unstructured":"Lafond M, Dondi R, El-Mabrouk N. The link between orthology relations and gene trees: a correction perspective. Algorithms Mol Biol. 2016;11(1):1.","journal-title":"Algorithms Mol Biol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-018-0121-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T19:13:49Z","timestamp":1660418029000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-018-0121-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,6]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["121"],"URL":"https:\/\/doi.org\/10.1186\/s13015-018-0121-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/201053","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,6]]},"assertion":[{"value":"21 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"2"}}