{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T20:12:33Z","timestamp":1770754353594,"version":"3.50.0"},"reference-count":30,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T00:00:00Z","timestamp":1628121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1616514"],"award-info":[{"award-number":["1616514"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1615573"],"award-info":[{"award-number":["1615573"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Duplication-Transfer-Loss (DTL) reconciliation is a widely used computational technique for understanding gene family evolution and inferring horizontal gene transfer (transfer for short) in microbes. However, most existing models and implementations of DTL reconciliation cannot account for the effect of unsampled or extinct species lineages on the evolution of gene families, likely affecting their accuracy. Accounting for the presence and possible impact of any unsampled species lineages, including those that are extinct, is especially important for inferring and studying horizontal transfer since many genes in the species lineages represented in the reconciliation analysis are likely to have been acquired through horizontal transfer from unsampled lineages. While models of DTL reconciliation that account for transfer from unsampled lineages have already been proposed, they use a relatively simple framework for transfer from unsampled lineages and cannot explicitly infer the location on the species tree of each unsampled or extinct lineage associated with an identified transfer event. Furthermore, there does not yet exist any systematic studies to assess the impact of accounting for unsampled lineages on the accuracy of DTL reconciliation. In this work, we address these deficiencies by (i) introducing an extended DTL reconciliation model, called the DTLx reconciliation model, that accounts for unsampled and extinct species lineages in a new, more functional manner compared to existing models, (ii) showing that optimal reconciliations under the new DTLx reconciliation model can be computed just as efficiently as under the fastest DTL reconciliation model, (iii) providing an efficient algorithm for sampling optimal DTLx reconciliations uniformly at random, (iv) performing the first systematic simulation study to assess the impact of accounting for unsampled lineages on the accuracy of DTL reconciliation, and (v) comparing the accuracies of inferring transfers from unsampled lineages under our new model and the only other previously proposed parsimony-based model for this problem.<\/jats:p>","DOI":"10.3390\/a14080231","type":"journal-article","created":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T09:35:32Z","timestamp":1628156132000},"page":"231","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages"],"prefix":"10.3390","volume":"14","author":[{"given":"Samson","family":"Weiner","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, University of Connecticut, Storrs, CT 06269, USA"}]},{"given":"Mukul S.","family":"Bansal","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, University of Connecticut, Storrs, CT 06269, USA"},{"name":"Institute for Systems Genomics, University of Connecticut, Storrs, CT 06269, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,8,5]]},"reference":[{"key":"ref_1","unstructured":"Tofigh, A. (2009). Using Trees to Capture Reticulate Evolution: Lateral Gene Transfers and Cancer Progression. [Ph.D. Thesis, KTH Royal Institute of Technology]."},{"key":"ref_2","first-page":"946","article-title":"Reconstructing genes evolution along a species tree","volume":"43","author":"Gorbunov","year":"2009","journal-title":"Molekuliarnaia Biologiia"},{"key":"ref_3","first-page":"93","article-title":"An Efficient Algorithm for Gene\/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers","volume":"Volume 6398","author":"Tannier","year":"2010","journal-title":"Research in Computational Molecular Biology\u2014Comparative Genomics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1109\/TCBB.2010.14","article-title":"Simultaneous Identification of Duplications and Lateral Gene Transfers","volume":"8","author":"Tofigh","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1038\/nature09649","article-title":"Rapid evolutionary innovation during an Archaean genetic expansion","volume":"469","author":"David","year":"2011","journal-title":"Nature"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1109\/TCBB.2012.79","article-title":"Simultaneous Identification of Duplications, Losses, and Lateral Gene Transfers","volume":"9","author":"Chen","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"283","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_8","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1093\/bioinformatics\/bts386","article-title":"Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees","volume":"28","author":"Stolzer","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"17513","DOI":"10.1073\/pnas.1202997109","article-title":"Phylogenetic modeling of lateral gene transfer reconstructs the pattern and relative timing of speciations","volume":"109","author":"Szollosi","year":"2012","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1093\/sysbio\/syt003","article-title":"Lateral Gene Transfer from the Dead","volume":"62","author":"Szollosi","year":"2013","journal-title":"Syst. Biol."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1089\/cmb.2013.0073","article-title":"Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss","volume":"20","author":"Bansal","year":"2013","journal-title":"J. Comput. Biol."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Scornavacca, C., Paprotny, W., Berry, V., and Ranwez, V. (2013). Representing a Set of Reconciliations in a Compact Way. J. Bioinform. Comput. Biol., 11.","DOI":"10.1142\/S0219720012500254"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"i87","DOI":"10.1093\/bioinformatics\/btu289","article-title":"Pareto-optimal phylogenetic tree reconciliation","volume":"30","author":"Wu","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1093\/sysbio\/syu007","article-title":"A Bayesian Method for Analyzing Lateral Gene Transfer","volume":"63","author":"Sjostrand","year":"2014","journal-title":"Syst. Biol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1093\/bioinformatics\/btu728","article-title":"Joint amalgamation of most parsimonious reconciled gene trees","volume":"31","author":"Scornavacca","year":"2015","journal-title":"Bioinformatics"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Jacox, E., Chauve, C., Szollosi, G.J., Ponty, Y., and Scornavacca, C. (2016). ecceTERA: Comprehensive gene tree-species tree reconciliation using parsimony. Bioinformatics, 32.","DOI":"10.1093\/bioinformatics\/btw105"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3214","DOI":"10.1093\/bioinformatics\/bty314","article-title":"RANGER-DTL 2.0: Rigorous reconstruction of gene-family evolution by duplication, transfer and loss","volume":"34","author":"Bansal","year":"2018","journal-title":"Bioinformatics"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1109\/TCBB.2017.2710342","article-title":"Exact Algorithms for Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees","volume":"16","author":"Kordi","year":"2019","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Merkle, D., Middendorf, M., and Wieseke, N. (2010). A parameter-adaptive dynamic programming approach for inferring cophylogenies. BMC Bioinform., 11.","DOI":"10.1186\/1471-2105-11-S1-S60"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Conow, C., Fielder, D., Ovadia, Y., and Libeskind-Hadas, R. (2010). Jane: A new tool for the cophylogeny reconstruction problem. Algorithms Mol. Biol., 5.","DOI":"10.1186\/1748-7188-5-16"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Donati, B., Baudet, C., Sinaimeri, B., Crescenzi, P., and Sagot, M.F. (2015). EUCALYPT: Efficient tree reconciliation enumerator. Algorithms Mol. Biol., 10.","DOI":"10.1186\/s13015-014-0031-3"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Santichaivekin, S., Yang, Q., Liu, J., Mawhorter, R., Jiang, J., Wesley, T., Wu, Y.C., and Libeskind-Hadas, R. (2020). eMPRess: A systematic cophylogeny reconciliation tool. Bioinformatics.","DOI":"10.1093\/bioinformatics\/btaa978"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1093\/gbe\/evs098","article-title":"Quantifying Homologous Replacement of Loci between Haloarchaeal Species","volume":"4","author":"Williams","year":"2012","journal-title":"Genome Biol. Evol."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1089\/cmb.2009.0240","article-title":"The Cophylogeny Reconstruction Problem Is NP-Complete","volume":"18","author":"Ovadia","year":"2011","journal-title":"J. Comput. Biol."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1089\/cmb.2008.0084","article-title":"On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem","volume":"16","author":"Charleston","year":"2009","journal-title":"J. Comput. Biol."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1007\/s10878-019-00396-z","article-title":"Gene tree reconciliation including transfers with replacement is NP-hard and FPT","volume":"38","author":"Tannier","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kordi, M., Kundu, S., and Bansal, M.S. (2019, January 7\u201310). On Inferring Additive and Replacing Horizontal Gene Transfers Through Phylogenetic Reconciliation. Proceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics, Niagara Falls, NY, USA.","DOI":"10.1145\/3307339.3342168"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Pudritz, R., Higgs, P., and Stone, J. (2007). Horizontal gene transfer, gene histories, and the root of the tree of life. Planetary Systems and the Origins of Life, Cambridge University Press. Cambridge Astrobiology.","DOI":"10.1017\/CBO9780511536120"},{"key":"ref_29","first-page":"1286","article-title":"Zombi: A phylogenetic simulator of trees, genomes and sequences that accounts for dead linages","volume":"36","author":"Tricou","year":"2019","journal-title":"Bioinformatics"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1093\/bioinformatics\/btu806","article-title":"Improved gene tree error correction in the presence of horizontal gene transfer","volume":"31","author":"Bansal","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/231\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:41:04Z","timestamp":1760164864000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,5]]},"references-count":30,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["a14080231"],"URL":"https:\/\/doi.org\/10.3390\/a14080231","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,5]]}}}