{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T23:09:28Z","timestamp":1768518568520,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Reconciliation methods compare gene trees and species trees to recover evolutionary events such as duplications, transfers and losses explaining the history and composition of genomes. It is well-known that gene trees inferred from molecular sequences can be partly erroneous due to incorrect sequence alignments as well as phylogenetic reconstruction artifacts such as long branch attraction. In practice, this leads reconciliation methods to overestimate the number of evolutionary events. Several methods have been proposed to circumvent this problem, by collapsing the unsupported edges and then resolving the obtained multifurcating nodes, or by directly rearranging the binary gene trees. Yet these methods have been defined for models of evolution accounting only for duplications and losses, i.e. can not be applied to handle prokaryotic gene families.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We propose a reconciliation method accounting for gene duplications, losses and horizontal transfers, that specifically takes into account the uncertainties in gene trees by rearranging their weakly supported edges. Rearrangements are performed on edges having a low confidence value, and are accepted whenever they improve the reconciliation cost. We prove useful properties on the dynamic programming matrix used to compute reconciliations, which allows to speed-up the tree space exploration when rearrangements are generated by Nearest Neighbor Interchanges (NNI) edit operations. Experiments on synthetic data show that gene trees modified by such NNI rearrangements are closer to the correct simulated trees and lead to better event predictions on average. Experiments on real data demonstrate that the proposed method leads to a decrease in the reconciliation cost and the number of inferred events. Finally on a dataset of 30 <jats:italic>k<\/jats:italic>\u2009gene families, this reconciliation method shows a ranking of prokaryotic phyla by transfer rates identical to that proposed by a different approach dedicated to transfer detection [BMCBIOINF 11:324, 2010, PNAS 109(13):4962\u20134967, 2012].<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Prokaryotic gene trees can now be reconciled with their species phylogeny while accounting for the uncertainty of the gene tree. More accurate and more precise reconciliations are obtained with respect to previous parsimony algorithms not accounting for such uncertainties [LNCS 6398:93\u2013108, 2010, BIOINF 28(12): i283\u2013i291, 2012].<\/jats:p>\n            <jats:p>A software implementing the method is freely available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/www.atgc-montpellier.fr\/Mowgli\/\" ext-link-type=\"uri\">http:\/\/www.atgc-montpellier.fr\/Mowgli\/<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1748-7188-8-12","type":"journal-article","created":{"date-parts":[[2013,4,8]],"date-time":"2013-04-08T10:17:25Z","timestamp":1365416245000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Reconciliation and local gene tree rearrangement can be of mutual profit"],"prefix":"10.1186","volume":"8","author":[{"given":"Thi Hau","family":"Nguyen","sequence":"first","affiliation":[]},{"given":"Vincent","family":"Ranwez","sequence":"additional","affiliation":[]},{"given":"St\u00e9phanie","family":"Pointet","sequence":"additional","affiliation":[]},{"given":"Anne-Muriel Arigon","family":"Chifolleau","sequence":"additional","affiliation":[]},{"given":"Jean-Philippe","family":"Doyon","sequence":"additional","affiliation":[]},{"given":"Vincent","family":"Berry","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,8]]},"reference":[{"issue":"10","key":"196_CR1","first-page":"2132","volume":"35","author":"MO Dayhoff","year":"1976","unstructured":"Dayhoff MO: The origin and evolution of protein superfamilies. Fed Proc. 1976, 35 (10): 2132-2138.","journal-title":"Fed Proc"},{"key":"196_CR2","first-page":"93","volume":"6398","author":"J-P Doyon","year":"2010","unstructured":"Doyon J-P, Scornavacca C, Gorbunov KY, Sz\u00f6ll\u00f6si G, Ranwez V, Berry V: An efficient algorithm for gene\/species trees parsimonious reconciliation with losses, duplications and transfers. RECOMB-CG 2010, LNCS. 2010, 6398: 93-108.","journal-title":"RECOMB-CG 2010, LNCS"},{"issue":"12","key":"196_CR3","doi-asserted-by":"publisher","first-page":"i283","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. In Bioinformatics. 2012, 28 (12): i283-i291. 10.1093\/bioinformatics\/bts225.","journal-title":"In Bioinformatics"},{"key":"196_CR4","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1145\/974614.974660","volume-title":"RECOMB \u201904","author":"M Hallett","year":"2004","unstructured":"Hallett M, Lagergren J, Tofigh A: Simultaneous identification of duplications and lateral transfers. RECOMB \u201904. Edited by: Bourne PE, Gusfield D. New York: ACM 2004, 347-356."},{"key":"196_CR5","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1145\/974614.974656","volume-title":"RECOMB","author":"P G\u00f3recki","year":"2004","unstructured":"G\u00f3recki P: Reconciliation problems for duplication, loss and horizontal gene transfer. RECOMB. Edited by: Bourne PE, Gusfield D. New York, NY, USA: ACM 2004, 316-325."},{"key":"196_CR6","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1186\/1748-7188-5-16","volume":"5","author":"C Conow","year":"2010","unstructured":"Conow C, Fielder D, Ovadia Y, Libeskind-Hadas R: Jane: a new tool for the cophylogeny reconstruction problem. Algorithms Mol Biol. 2010, 5: 16.","journal-title":"Algorithms Mol Biol"},{"issue":"2","key":"196_CR7","first-page":"517","volume":"8","author":"A Tofigh","year":"2011","unstructured":"Tofigh A, Hallett M, Lagergren J: Simultaneous identification of duplications and lateral gene transfers. IEEE\/ACMTCBB. 2011, 8 (2): 517-535.","journal-title":"IEEE\/ACMTCBB"},{"issue":"7328","key":"196_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1038\/nature09649","volume":"469","author":"LA David","year":"2011","unstructured":"David LA, Alm EJ: Rapid evolutionary innovation during an archaean genetic expansion. Nature. 2011, 469 (7328): 93-96.","journal-title":"Nature"},{"key":"196_CR9","doi-asserted-by":"publisher","first-page":"132","DOI":"10.2307\/2412519","volume":"28","author":"M Goodman","year":"1979","unstructured":"Goodman M, Czelusniak J, Moore GW, Romero Herrera A, Matsuda G: Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Syst Zool. 1979, 28: 132-163. 10.2307\/2412519.","journal-title":"Syst Zool"},{"key":"196_CR10","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/mpev.1999.0676","volume":"14","author":"RD Page","year":"2000","unstructured":"Page RD: Extracting species trees from complex gene trees: reconciled trees and vertebrate phylogeny. Mol Phylogenet Evol. 2000, 14: 89-106.","journal-title":"Mol Phylogenet Evol"},{"issue":"3","key":"196_CR11","first-page":"729","volume":"30","author":"B Ma","year":"2001","unstructured":"Ma B, Li M, Zhang L: From gene trees to species trees. SIComput, AMJ. 2001, 30 (3): 729-752.","journal-title":"SIComput, AMJ"},{"key":"196_CR12","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/974614.974659","volume-title":"Proceedings of the Eighth Annual International Conference on Resaerch in Computational Molecular Biology","author":"L Nakhleh","year":"2004","unstructured":"Nakhleh L, Warnow T, Linder CR: Reconstructing reticulate evolution in species: theory and practice. Proceedings of the Eighth Annual International Conference on Resaerch in Computational Molecular Biology. 2004, 337-346. RECOMB \u201904. New York: ACM,"},{"issue":"2","key":"196_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1502793.1502796","volume":"56","author":"L Arvestad","year":"2009","unstructured":"Arvestad L, Lagergren J, Sennblad B: The gene evolution model and computing its associated probabilities. J ACM. 2009, 56 (2): 1-44.","journal-title":"J ACM"},{"issue":"5","key":"196_CR14","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 Bioinformatics. 2011, 12 (5): 392-400.","journal-title":"Brief Bioinformatics"},{"issue":"1","key":"196_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1089\/cmb.2009.0240","volume":"18","author":"Y Ovadia","year":"2011","unstructured":"Ovadia Y, Fielder D, Conow C, Libeskind-Hadas R: The cophylogeny reconstruction problem is NP-complete. Comp J Biol. 2011, 18 (1): 59-65. 10.1089\/cmb.2009.0240.","journal-title":"Comp J Biol"},{"issue":"1","key":"196_CR16","first-page":"105","volume":"16","author":"R Libeskind-Hadas","year":"2009","unstructured":"Libeskind-Hadas R, Charleston MA: On the computational complexity of the reticulate cophylogeny reconstruction problem. JCB. 2009, 16 (1): 105-117.","journal-title":"JCB"},{"key":"196_CR17","volume-title":"Using Trees to Capture Reticulate Evolution, Lateral Gene Transfers and Cancer Progression. PhD thesis, Royal, KTH,","author":"A Tofigh","year":"2009","unstructured":"Tofigh A: Using Trees to Capture Reticulate Evolution, Lateral Gene Transfers and Cancer Progression. PhD thesis, Royal, KTH, . 2009, Sweden: Institute of Technology,"},{"key":"196_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-1-61779-585-5_2","volume":"856","author":"GJ Szo\u030bll\u00f6si","year":"2012","unstructured":"Szo\u030bll\u00f6si GJ, : Modeling gene family evolution and reconciling phylogenetic discord. Methods Mol Biol. 2012, 856: 29-51.","journal-title":"Methods Mol Biol"},{"issue":"2","key":"196_CR19","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1089\/cmb.2006.13.320","volume":"13","author":"D Durand","year":"2006","unstructured":"Durand D, Halldorsson BV, : A hybrid micro-macroevolutionary approach to gene tree reconstruction. Comput J Biol. 2006, 13 (2): 320-335. 10.1089\/cmb.2006.13.320.","journal-title":"Comput J Biol"},{"issue":"7","key":"196_CR20","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":"2","key":"196_CR21","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/s00239-005-0096-1","volume":"63","author":"AC Berglund-Sonnhammer","year":"2006","unstructured":"Berglund-Sonnhammer AC, Steffansson P, Betts MJ, Liberles DA: Optimal gene trees from sequences and species trees using a soft interpretation of parsimony. Mol J Evol. 2006, 63 (2): 240-250. 10.1007\/s00239-005-0096-1.","journal-title":"Mol J Evol"},{"key":"196_CR22","first-page":"235","volume":"4112","author":"W Chang","year":"2006","unstructured":"Chang W, Eulenstein O: Reconciling gene tree with apparent polytomies. COCOON, LNCS. 2006, 4112: 235-244.","journal-title":"COCOON, LNCS"},{"key":"196_CR23","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, : Reconciliation with non-binary species trees. Comput J Biol. 2008, 15: 981-1006. 10.1089\/cmb.2008.0092.","journal-title":"Comput J Biol"},{"key":"196_CR24","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-642-21260-4_23","volume-title":"Proceedings of the 7th International Conference on Bioinformatics Research and Applications","author":"R Chaudhary","year":"2011","unstructured":"Chaudhary R, Burleigh JG, Eulenstein O: Algorithms for rapid error correction for the gene duplication problem. Proceedings of the 7th International Conference on Bioinformatics Research and Applications. 2011, 227-239. ISBRA\u201911. Berlin, Heidelberg: Springer-Verlag,"},{"key":"196_CR25","first-page":"1201.3995v2","volume-title":"ArXiv","author":"Y Zheng","year":"2012","unstructured":"Zheng Y, Wu T, Zhang L: Reconciliation of gene and species trees With Polytomies. ArXiv. 2012, 1201.3995v2-[q-bio.PE],"},{"key":"196_CR26","first-page":"106","volume-title":"WABI 2012, LNBI 7534","author":"M Lafond","year":"2012","unstructured":"Lafond M, Krister Swenson M, El-Mabrouk N: An optimal reconciliation algorithm for gene trees with polytomies. WABI 2012, LNBI 7534. Edited by: Tang J, Raphael B, Raphael B , Tang J . 2012, 106-122. Berlin Heidelberg: Springer-Verlag,"},{"key":"196_CR27","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1093\/bioinformatics\/bts386","volume":"28","author":"M Stolzer","year":"2012","unstructured":"Stolzer M, Lai H, Xu M, Sathaye D, Vernot B, Durand D: Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees. Bioinformatics. 2012, 28: 409-415. 10.1093\/bioinformatics\/bts386.","journal-title":"Bioinformatics"},{"issue":"Suppl 10","key":"196_CR28","doi-asserted-by":"publisher","first-page":"S14","DOI":"10.1186\/1471-2105-13-S10-S14","volume":"13","author":"P G\u00f3recki","year":"2012","unstructured":"G\u00f3recki P, Eulenstein O: Algorithms: simultaneous error-correction and rooting for gene tree reconciliation and the gene duplication problem. Bioinformatics, BMC, . 2012, 13 (Suppl 10): S14-10.1186\/1471-2105-13-S10-S14.","journal-title":"Bioinformatics, BMC,"},{"key":"196_CR29","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1186\/1471-2105-11-324","volume":"11","author":"S Abby","year":"2010","unstructured":"Abby S, Tannier E, Gouy M, Daubin V: Detecting lateral gene transfers by statistical reconciliation of phylogenetic forests. Bioinformatics, BMC. 2010, 11: 324-10.1186\/1471-2105-11-324.","journal-title":"Bioinformatics, BMC"},{"issue":"13","key":"196_CR30","doi-asserted-by":"publisher","first-page":"4962","DOI":"10.1073\/pnas.1116871109","volume":"109","author":"S Abby","year":"2012","unstructured":"Abby S, Tannier E, Gouy M, Daubin V: Lateral gene transfer as a support for the tree of life. PNAS. 2012, 109 (13): 4962-4967.","journal-title":"PNAS"},{"key":"196_CR31","volume-title":"Phylogenetics, volume 24 of Oxford Lecture Series in Mathematics and its Applications","author":"C Semple","year":"2003","unstructured":"Semple C, Steel MA: Phylogenetics, volume 24 of Oxford Lecture Series in Mathematics and its Applications. 2003, New York, USA: Oxford University Press,"},{"key":"196_CR32","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1093\/bioinformatics\/19.2.301","volume":"19","author":"MJ Sanderson","year":"2003","unstructured":"Sanderson MJ: inferring absolute rates of evolution and divergence times in the absence of a molecular clock. Bioinformatics. 2003, 19: 301-302.","journal-title":"Bioinformatics"},{"key":"196_CR33","volume-title":"Inferring Phylogenies","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein J: Inferring Phylogenies. 2004, Sunderland: Sinauer Associates,"},{"key":"196_CR34","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth DE: The Art of Computer Programming. 1998, Redwood City: Addison-Wesley Longman Publishing Co., Inc.,"},{"key":"196_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/aoms\/1177730285","volume":"19","author":"DG Kendall","year":"1948","unstructured":"Kendall DG: On the generalized birth-and-death process. Ann Math Stat. 1948, 19: 1-15. 10.1214\/aoms\/1177730285.","journal-title":"Ann Math Stat"},{"key":"196_CR36","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1080\/10635150701546231","volume":"56","author":"N Galtier","year":"2007","unstructured":"Galtier N: A model of horizontal gene transfer and the bacterial phylogeny problem. Syst Biol. 2007, 56: 633-642.","journal-title":"Syst Biol"},{"issue":"3","key":"196_CR37","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1093\/bioinformatics\/13.3.235","volume":"13","author":"A Rambaut","year":"1997","unstructured":"Rambaut A, Grass NC: Seq-gen: an application for the monte carlo simulation of dna sequence evolution along phylogenetic trees. Bioinformatics. 1997, 13 (3): 235-238. 10.1093\/bioinformatics\/13.3.235.","journal-title":"Bioinformatics"},{"issue":"21","key":"196_CR38","doi-asserted-by":"publisher","first-page":"2688","DOI":"10.1093\/bioinformatics\/btl446","volume":"22","author":"A Stamatakis","year":"2006","unstructured":"Stamatakis A: Raxml-vi-hpc: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics. 2006, 22 (21): 2688-2690.","journal-title":"Bioinformatics"},{"key":"196_CR39","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"DF Robinson","year":"1981","unstructured":"Robinson DF, Foulds LR: Comparison of phylogenetic trees. Math Biosci. 1981, 53: 131-147. 10.1016\/0025-5564(81)90043-2.","journal-title":"Math Biosci"},{"issue":"Suppl10","key":"196_CR40","doi-asserted-by":"publisher","first-page":"S3","DOI":"10.1186\/1471-2105-10-S6-S3","volume":"6","author":"S Penel","year":"2009","unstructured":"Penel S, Arigon AM, Dufayard JF, Sertier AS, Daubin V, Duret L, Gouy M, Perriere G: Databases of homologous gene families for comparative genomics. Bioinformatics, BMC. 2009, 6 (Suppl10): S3.","journal-title":"Bioinformatics, BMC"},{"issue":"43","key":"196_CR41","doi-asserted-by":"publisher","first-page":"17513","DOI":"10.1073\/pnas.1202997109","volume":"109","author":"GJ Szo\u030bll\u00f6si","year":"2012","unstructured":"Szo\u030bll\u00f6si GJ, Boussau B, Tannier E, Daubin V: Phylogenetic modeling of lateral gene transfer reconstructs the pattern and relative timing of speciations. PNAS. 2012, 109 (43): 17513-17518.","journal-title":"PNAS"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-8-12.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T01:10:41Z","timestamp":1630545041000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-8-12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,8]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["196"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-8-12","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,8]]},"assertion":[{"value":"17 December 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2013","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}