{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:24:54Z","timestamp":1772166294015,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,7,30]],"date-time":"2023-07-30T00:00:00Z","timestamp":1690675200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,30]],"date-time":"2023-07-30T00:00:00Z","timestamp":1690675200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Reconciling a non-binary gene tree with a binary species tree can be done efficiently in the absence of horizontal gene transfers, but becomes NP-hard in the presence of gene transfers. Here, we focus on the special case of\n                    <jats:italic>endosymbiotic gene transfers<\/jats:italic>\n                    (EGT), i.e. transfers between the mitochondrial and nuclear genome of the same species. More precisely, given a multifurcated (non-binary) gene tree with leaves labeled 0 or 1 depending on whether the corresponding genes belong to the mitochondrial or nuclear genome of the corresponding species, we investigate the problem of inferring a most parsimonious Duplication, Loss and EGT (DLE) Reconciliation of any binary refinement of the tree. We present a general two-steps method: ignoring the 0\u20131 labeling of leaves, output a binary resolution minimizing the Duplication and Loss (DL) Reconciliation and then, for such resolution, assign a known number of 0s and 1s to the leaves in a way minimizing EGT events. While the first step corresponds to the well studied non-binary DL-Reconciliation problem, the complexity of the label assignment problem corresponding to the second step is unknown. We show that this problem is NP-complete, even when the tree is restricted to a single polytomy, and even if transfers can occur in only one direction. We present a general algorithm solving each polytomy separately, which is shown optimal for a unitary cost of operation, and a polynomial-time algorithm for solving a polytomy in the special case where genes are specific to a single genome (mitochondrial or nuclear) in all but one species. This work represents the first algorithmic study for reconciliation with endosymbiotic gene transfers in the case of a multifurcated gene tree.\n                  <\/jats:p>","DOI":"10.1186\/s13015-023-00231-5","type":"journal-article","created":{"date-parts":[[2023,7,30]],"date-time":"2023-07-30T14:01:55Z","timestamp":1690725715000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the complexity of non-binary tree reconciliation with endosymbiotic gene transfer"],"prefix":"10.1186","volume":"18","author":[{"given":"Mathieu","family":"Gascon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,30]]},"reference":[{"issue":"7","key":"231_CR1","doi-asserted-by":"publisher","first-page":"R141","DOI":"10.1186\/gb-2007-8-7-r141","volume":"8","author":"MW Hahn","year":"2007","unstructured":"Hahn MW. Bias in phylogenetic tree reconciliation methods: implications for vertebrate genome evolution. Genome Biol. 2007;8(7):R141.","journal-title":"Genome Biol"},{"issue":"SI\u20131","key":"231_CR2","doi-asserted-by":"publisher","first-page":"i120","DOI":"10.1093\/bioinformatics\/btab328","volume":"37","author":"Y Anselmetti","year":"2021","unstructured":"Anselmetti Y, El-Mabrouk N, Lafond M, Ouangraoua A. Gene tree and species tree reconciliation with endosymbiotic gene transfer. Bioinformatics. 2021;37(SI\u20131):i120\u201332.","journal-title":"Bioinformatics."},{"issue":"1","key":"231_CR3","doi-asserted-by":"publisher","first-page":"33782","DOI":"10.1038\/srep33782","volume":"6","author":"J Sabir","year":"2007","unstructured":"Sabir J, Jansen R, Arasappan D, et al. The nuclear genome of Rhazya stricta and the evolution of alkaloid diversity in a medically relevant clade of Apocynaceae. Sci Rep. 2007;6(1):33782.","journal-title":"Sci Rep"},{"key":"231_CR4","doi-asserted-by":"crossref","unstructured":"El-Mabrouk N, Noutahi E. Gene Family Evolution-An Algorithmic Framework. In: Bioinformatics and Phylogenetics: Seminal Contributions of Bernard Moret. t. warnow ed. Cham: Springer International Publishing; 2019. p. 87\u2013119.","DOI":"10.1007\/978-3-030-10837-3_5"},{"key":"231_CR5","unstructured":"Lafond M, Noutahi E, El-Mabrouk N. Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost. In: Grossi R, Lewenstein M, editors. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). vol.\u00a054 of Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik; 2016. pp. 14:1\u201314:12."},{"key":"231_CR6","doi-asserted-by":"crossref","unstructured":"Kordi M, Bansal MS. On the complexity of Duplication-Transfer-Loss reconciliation with non-binary gene trees. IEEE\/ACM Transactions on Computational Biology and Bioinformatics. 2016; pp. 587\u2013599.","DOI":"10.1109\/TCBB.2015.2511761"},{"issue":"7","key":"231_CR7","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1093\/bioinformatics\/btw778","volume":"33","author":"E Jacox","year":"2017","unstructured":"Jacox E, Weller M, Tannier E, Scornavacca C. Resolution and reconciliation of non-binary gene trees with transfers, duplications and losses. Bioinformatics. 2017;33(7):980\u20137.","journal-title":"Bioinformatics."},{"key":"231_CR8","doi-asserted-by":"crossref","unstructured":"Lai H, Stolzer M, Durand D. Fast heuristics for resolving weakly supported branches using duplication, transfers, and losses. In: Proceedings of RECOMB-CG; 2017. pp. 298\u2013320.","DOI":"10.1007\/978-3-319-67979-2_16"},{"key":"231_CR9","doi-asserted-by":"crossref","unstructured":"Kordi M, Bansal MS. Exact algorithms for duplication-transfer-loss reconciliation with non-binary gene trees. IEEE\/ACM Transactions on Computational Biology and Bioinformatics. 2017; pp. 1077\u20131090.","DOI":"10.1109\/TCBB.2017.2710342"},{"issue":"11","key":"231_CR10","first-page":"1","volume":"14","author":"S Kannan","year":"2014","unstructured":"Kannan S, Rogozin I, Koonin E. MitoCOGs: clusters of orthologous genes from mitochondria and implications for the evolution of eukaryotes. BMC Evol Biol. 2014;14(11):1\u201316.","journal-title":"BMC Evol Biol"},{"key":"231_CR11","doi-asserted-by":"crossref","unstructured":"Chauve C, El-Mabrouk N. New perspectives on gene family evolution: losses in reconciliation and a link with supertrees. In: Lecture notes in computer science. vol. 5541 of RECOMB; 2009. pp. 46\u201358.","DOI":"10.1007\/978-3-642-02008-7_4"},{"issue":"1","key":"231_CR12","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1093\/sysbio\/syx046","volume":"67","author":"C Colijn","year":"2018","unstructured":"Colijn C, Plazzotta G. A metric on phylogenetic tree shapes. Syst Biol. 2018;67(1):113\u201326.","journal-title":"Syst Biol"},{"key":"231_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2018.08.006","volume":"760","author":"M Lafond","year":"2018","unstructured":"Lafond M, El-Mabrouk N, Huber KT, Moulton V. The complexity of comparing mutiply-labelled trees by extending phylogenetic-tree metrics. Theor Comput Sci. 2018;760:15\u201334.","journal-title":"Theor Comput Sci"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00231-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-023-00231-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00231-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,30]],"date-time":"2023-07-30T14:02:03Z","timestamp":1690725723000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-023-00231-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,30]]},"references-count":13,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["231"],"URL":"https:\/\/doi.org\/10.1186\/s13015-023-00231-5","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2753083\/v1","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,30]]},"assertion":[{"value":"29 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This declaration is not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"9"}}