{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:28:45Z","timestamp":1773275325450,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"S20","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":16,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n<jats:title>Background<\/jats:title>\n<jats:p>Maximum parsimony reconciliation in the duplication-transfer-loss model is widely used in studying the evolutionary histories of genes and species and in studying coevolution of parasites and their hosts and pairs of symbionts. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of reconciliations can grow exponentially in the size of the trees. An understanding of the space of maximum parsimony reconciliations is necessary to determine whether a single reconciliation can adequately represent the space or whether multiple representative reconciliations are needed.<\/jats:p>\n<\/jats:sec><jats:sec>\n<jats:title>Results<\/jats:title>\n<jats:p>We show that for any instance of the reconciliation problem, the distribution of pairwise distances can be computed exactly by an efficient polynomial-time algorithm with respect to several different distance metrics. We describe the algorithm, analyze its asymptotic worst-case running time, and demonstrate its utility and viability on a large biological dataset.<\/jats:p>\n<\/jats:sec><jats:sec>\n<jats:title>Conclusions<\/jats:title>\n<jats:p>This result provides new insights into the structure of the space of maximum parsimony reconciliations. These insights are likely to be useful in the wide range of applications that employ reconciliation methods.<\/jats:p>\n<\/jats:sec>","DOI":"10.1186\/s12859-019-3203-9","type":"journal-article","created":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T01:02:24Z","timestamp":1576544544000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An efficient exact algorithm for computing all pairwise distances between reconciliations in the duplication-transfer-loss model"],"prefix":"10.1186","volume":"20","author":[{"given":"Santi","family":"Santichaivekin","sequence":"first","affiliation":[]},{"given":"Ross","family":"Mawhorter","sequence":"additional","affiliation":[]},{"given":"Ran","family":"Libeskind-Hadas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"issue":"1","key":"3203_CR1","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1109\/TCBB.2018.2849732","volume":"16","author":"J Haack","year":"2019","unstructured":"Haack J, Ramirez A, Zupke E, Wu Y, Libeskind-Hadas R. Computing the diameter of the space of maximum parsimony reconciliations in the duplication-transfer-loss model. IEEE\/ACM Trans Comput Biol Bioinform. 2019; 16(1):14\u201322. https:\/\/doi.org\/10.1109\/TCBB.2018.2849732.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"3203_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-16181-0_9","volume":"6398","author":"J-P Doyon","year":"2011","unstructured":"Doyon J-P, Scornavacca C, Gorbunov KY, Sz\u00f6llosi J G, Ranwez V, Berry V. An efficient algorithm for gene\/species trees parsimonious reconciliation with losses, duplications and transfers. Comp Genom. 2011; 6398:93\u2013108.","journal-title":"Comp Genom"},{"issue":"2","key":"3203_CR3","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1109\/TCBB.2010.14","volume":"8","author":"A Tofigh","year":"2011","unstructured":"Tofigh A, Hallett MT, Lagergren J. Simultaneous identification of duplications and lateral gene transfers. IEEE\/ACM Trans Comp Bio Bioinfo. 2011; 8(2):517\u201335.","journal-title":"IEEE\/ACM Trans Comp Bio Bioinfo"},{"issue":"5","key":"3203_CR4","doi-asserted-by":"publisher","first-page":"1515","DOI":"10.1109\/TCBB.2012.79","volume":"9","author":"Z. -Z. Chen","year":"2012","unstructured":"Chen Z. -Z., Deng F, Wang L. Simultaneous identification of duplications, losses, and lateral gene transfers. IEEE\/ACM Trans Comput Biol Bioinform. 2012; 9(5):1515\u201328.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"3203_CR5","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:93\u201396.","journal-title":"Nature"},{"issue":"12","key":"3203_CR6","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1093\/bioinformatics\/btu289","volume":"30","author":"R Libeskind-Hadas","year":"2014","unstructured":"Libeskind-Hadas R, Wu Y-C, Bansal MS, Kellis M. Pareto-optimal phylogenetic tree reconciliation. Bioinformatics. 2014; 30(12):87\u201395.","journal-title":"Bioinformatics"},{"issue":"02","key":"3203_CR7","doi-asserted-by":"publisher","first-page":"1250025","DOI":"10.1142\/S0219720012500254","volume":"11","author":"C Scornavacca","year":"2013","unstructured":"Scornavacca C, Paprotny W, Berry V, Ranwez V. Representing a set of reconciliations in a compact way. J Bioinforma Comput Biol. 2013; 11(02):1250025.","journal-title":"J Bioinforma Comput Biol"},{"issue":"10","key":"3203_CR8","doi-asserted-by":"publisher","first-page":"73667","DOI":"10.1371\/journal.pone.0073667","volume":"8","author":"T-H Nguyen","year":"2013","unstructured":"Nguyen T-H, Ranwez V, Berry V, Scornavacca C. Support measures to estimate the reliability of evolutionary events predicted by reconciliation methods. PLoS ONE. 2013; 8(10):73667.","journal-title":"PLoS ONE"},{"key":"3203_CR9","volume-title":"Clustering the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model","year":"2017","unstructured":"Ozdemir A, Sheely M, Bork D, Cheng R, Hulett R, Sung J, Wang J, Libeskind-Hadas R. In: Figueiredo D, Mart\u00edn-Vide C, Pratas D, Vega-Rodr\u00edguez MA, (eds).Clustering the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model. Cham: Springer; 2017, pp. 127\u201339."},{"key":"3203_CR10","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1109\/TCBB.2016.2537319","volume":"15","author":"W Ma","year":"2016","unstructured":"Ma W, Smirnov D, Forman J, Schweickart A, Slocum C, Srinivasan S, Libeskind-Hadas R. DTL-RnB: Algorithms and tools for summarizing the space of DTL reconciliations. IEEE\/ACM Trans Comp Bio Bioinfo. 2016; 15:411\u201321.","journal-title":"IEEE\/ACM Trans Comp Bio Bioinfo"},{"key":"3203_CR11","doi-asserted-by":"crossref","unstructured":"Haack J, Ramirez A, Zupke E, Wu Y, Libeskind-Hadas R. Computing the diameter of the space of maximum parsimony reconciliations in the duplication-transfer-loss model. IEEE Trans Comput Biol Bioinforma. 2018. Special Issue for APBC 2018.","DOI":"10.1109\/TCBB.2018.2849732"},{"key":"3203_CR12","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1093\/sysbio\/syy075","volume":"68","author":"KT Huber","year":"2018","unstructured":"Huber KT, Moulton V, Sagot M. -F., Sinaimeri B. Exploring and Visualizing Spaces of Tree Reconciliations. Syst Biol. 2018; 68:607\u201318.","journal-title":"Syst Biol"},{"key":"3203_CR13","unstructured":"Tofigh A. Using trees to capture reticulate evolution: Lateral gene transfers and cancer progression. PhD thesis, KTH Royal Institute of Technology. 2009."},{"issue":"3","key":"3203_CR14","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1186\/s12859-017-1463-9","volume":"18","author":"W Ma","year":"2017","unstructured":"Ma W, Smirnov D, Libeskind-Hadas R. DTL reconciliation repair. BMC Bioinformatics. 2017; 18(3):76.","journal-title":"BMC Bioinformatics"},{"key":"3203_CR15","first-page":"279","volume":"8","author":"L Addario-Berry","year":"2003","unstructured":"Addario-Berry L, Hallett MT, Lagergren J. Towards identifying lateral gene transfer events. Pac Symp Biocomput. 2003; 8:279\u201390.","journal-title":"Pac Symp Biocomput"},{"key":"3203_CR16","doi-asserted-by":"publisher","unstructured":"Grueter M, Duran K, Ramalingam R, Libeskind-Hadas R. Reconciliation reconsidered: In search of a most representative reconciliation in the duplication-transfer-loss model. In: Proceedings of the 17th Asia Pacific Bioinformatics Conference: 2019. https:\/\/doi.org\/10.1109\/tcbb.2019.2942015.","DOI":"10.1109\/tcbb.2019.2942015"},{"key":"3203_CR17","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ipl.2018.04.001","volume":"136","author":"KT Huber","year":"2018","unstructured":"Huber KT, Moulton V, Sagot M. -F., Sinaimeri B. Geometric medians in reconciliation spaces of phylogenetic trees. Inf Process Lett. 2018; 136:96\u2013101.","journal-title":"Inf Process Lett"},{"issue":"141","key":"3203_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1090\/S0025-5718-1978-0468306-4","volume":"32","author":"S Winograd","year":"1978","unstructured":"Winograd S. On computing the Discrete Fourier Transform. Math Comput. 1978; 32(141):175\u201399.","journal-title":"Math Comput"},{"issue":"3","key":"3203_CR19","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1109\/TCBB.2018.2838667","volume":"16","author":"Laura Urbini","year":"2019","unstructured":"Urbini L, Sinaimeri B, Matias C, Sagot M. Exploring the robustness of the parsimonious reconciliation method in host-symbiont cophylogeny. IEEE\/ACM Trans Comput Biol Bioinforma. 2018; 1. https:\/\/doi.org\/10.1109\/tcbb.2018.2838667.","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"issue":"2","key":"3203_CR20","doi-asserted-by":"publisher","first-page":"3336","DOI":"10.1016\/j.eswa.2008.01.039","volume":"36","author":"H-S Park","year":"2009","unstructured":"Park H-S, Jun C-H. A simple and fast algorithm for k-medoids clustering. Expert Syst Appl. 2009; 36(2):3336\u201341.","journal-title":"Expert Syst Appl"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3203-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-3203-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3203-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T00:14:32Z","timestamp":1608077672000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-3203-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":20,"journal-issue":{"issue":"S20","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["3203"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-3203-9","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"17 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"636"}}