Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages
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 effe...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/8/231 |
| _version_ | 1797524954688782336 |
|---|---|
| author | Samson Weiner Mukul S. Bansal |
| author_facet | Samson Weiner Mukul S. Bansal |
| author_sort | Samson Weiner |
| collection | DOAJ |
| description | 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 <i>DTLx reconciliation model</i>, 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. |
| first_indexed | 2024-03-10T09:04:55Z |
| format | Article |
| id | doaj.art-0e325cba459d447cbe26b0b968dd9bae |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T09:04:55Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-0e325cba459d447cbe26b0b968dd9bae2023-11-22T06:27:39ZengMDPI AGAlgorithms1999-48932021-08-0114823110.3390/a14080231Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled LineagesSamson Weiner0Mukul S. Bansal1Department of Computer Science & Engineering, University of Connecticut, Storrs, CT 06269, USADepartment of Computer Science & Engineering, University of Connecticut, Storrs, CT 06269, USADuplication-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 <i>DTLx reconciliation model</i>, 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.https://www.mdpi.com/1999-4893/14/8/231Duplication-Transfer-Loss reconciliationextinct and unsampled lineagesalgorithmshorizontal gene transfer |
| spellingShingle | Samson Weiner Mukul S. Bansal Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages Algorithms Duplication-Transfer-Loss reconciliation extinct and unsampled lineages algorithms horizontal gene transfer |
| title | Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages |
| title_full | Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages |
| title_fullStr | Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages |
| title_full_unstemmed | Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages |
| title_short | Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages |
| title_sort | improved duplication transfer loss reconciliation with extinct and unsampled lineages |
| topic | Duplication-Transfer-Loss reconciliation extinct and unsampled lineages algorithms horizontal gene transfer |
| url | https://www.mdpi.com/1999-4893/14/8/231 |
| work_keys_str_mv | AT samsonweiner improvedduplicationtransferlossreconciliationwithextinctandunsampledlineages AT mukulsbansal improvedduplicationtransferlossreconciliationwithextinctandunsampledlineages |