Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss
Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While duplication–loss (DL) reconciliation leads to a unique maximum-parsimony...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Mary Ann Liebert
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99233 https://orcid.org/0000-0001-8294-9364 |
| _version_ | 1811076040171192320 |
|---|---|
| author | Bansal, Mukul S. Alm, Eric J. Kellis, Manolis |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Bansal, Mukul S. Alm, Eric J. Kellis, Manolis |
| author_sort | Bansal, Mukul S. |
| collection | MIT |
| description | Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While duplication–loss (DL) reconciliation leads to a unique maximum-parsimony solution, duplication-transfer-loss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult to infer the true evolutionary history of the gene family. This problem is further exacerbated by the fact that different event cost assignments yield different sets of optimal reconciliations. Here, we present an effective, efficient, and scalable method for dealing with these fundamental problems in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We show that even gene trees with only a few dozen genes often have millions of optimal reconciliations and present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn[superscript 2]) time per sample, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mappings and event assignments and to investigate the impact of varying event costs. We apply our method to a biological dataset of approximately 4700 gene trees from 100 taxa and observe that 93% of event assignments and 73% of mappings remain consistent across different multiple optima. Our analysis represents the first systematic investigation of the space of optimal DTL reconciliations and has many important implications for the study of gene family evolution. |
| first_indexed | 2024-09-23T10:15:09Z |
| format | Article |
| id | mit-1721.1/99233 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:15:09Z |
| publishDate | 2015 |
| publisher | Mary Ann Liebert |
| record_format | dspace |
| spelling | mit-1721.1/992332022-09-26T16:45:01Z Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss Bansal, Mukul S. Alm, Eric J. Kellis, Manolis Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Biological Engineering Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bansal, Mukul S. Alm, Eric J. Kellis, Manolis Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While duplication–loss (DL) reconciliation leads to a unique maximum-parsimony solution, duplication-transfer-loss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult to infer the true evolutionary history of the gene family. This problem is further exacerbated by the fact that different event cost assignments yield different sets of optimal reconciliations. Here, we present an effective, efficient, and scalable method for dealing with these fundamental problems in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We show that even gene trees with only a few dozen genes often have millions of optimal reconciliations and present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn[superscript 2]) time per sample, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mappings and event assignments and to investigate the impact of varying event costs. We apply our method to a biological dataset of approximately 4700 gene trees from 100 taxa and observe that 93% of event assignments and 73% of mappings remain consistent across different multiple optima. Our analysis represents the first systematic investigation of the space of optimal DTL reconciliations and has many important implications for the study of gene family evolution. National Science Foundation (U.S.) (CAREER Award 0644282) National Institutes of Health (U.S.) (Grant RC2 HG005639) National Science Foundation (U.S.). Assembling the Tree of Life (Program) (Grant 0936234) 2015-10-13T18:38:32Z 2015-10-13T18:38:32Z 2013-09 Article http://purl.org/eprint/type/JournalArticle 1066-5277 1557-8666 http://hdl.handle.net/1721.1/99233 Bansal, Mukul S., Eric J. Alm, and Manolis Kellis. “Reconciliation Revisited: Handling Multiple Optima When Reconciling with Duplication, Transfer, and Loss.” Journal of Computational Biology 20, no. 10 (October 2013): 738–754. © 2013 Mary Ann Liebert, Inc. https://orcid.org/0000-0001-8294-9364 en_US http://dx.doi.org/10.1089/cmb.2013.0073 Journal of Computational Biology Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Mary Ann Liebert Mary Ann Leibert |
| spellingShingle | Bansal, Mukul S. Alm, Eric J. Kellis, Manolis Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss |
| title | Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss |
| title_full | Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss |
| title_fullStr | Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss |
| title_full_unstemmed | Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss |
| title_short | Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss |
| title_sort | reconciliation revisited handling multiple optima when reconciling with duplication transfer and loss |
| url | http://hdl.handle.net/1721.1/99233 https://orcid.org/0000-0001-8294-9364 |
| work_keys_str_mv | AT bansalmukuls reconciliationrevisitedhandlingmultipleoptimawhenreconcilingwithduplicationtransferandloss AT almericj reconciliationrevisitedhandlingmultipleoptimawhenreconcilingwithduplicationtransferandloss AT kellismanolis reconciliationrevisitedhandlingmultipleoptimawhenreconcilingwithduplicationtransferandloss |