Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model
Abstract Background Reconciliation methods are widely used to explain incongruence between a gene tree and species tree. However, the common approach of inferring maximum parsimony reconciliations (MPRs) relies on user-defined costs for each type of event, which can be difficult to estimate. Prior w...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2019-12-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s12859-019-3206-6 |
| _version_ | 1818392571061207040 |
|---|---|
| author | Ross Mawhorter Nuo Liu Ran Libeskind-Hadas Yi-Chieh Wu |
| author_facet | Ross Mawhorter Nuo Liu Ran Libeskind-Hadas Yi-Chieh Wu |
| author_sort | Ross Mawhorter |
| collection | DOAJ |
| description | Abstract Background Reconciliation methods are widely used to explain incongruence between a gene tree and species tree. However, the common approach of inferring maximum parsimony reconciliations (MPRs) relies on user-defined costs for each type of event, which can be difficult to estimate. Prior work has explored the relationship between event costs and maximum parsimony reconciliations in the duplication-loss and duplication-transfer-loss models, but no studies have addressed this relationship in the more complicated duplication-loss-coalescence model. Results We provide a fixed-parameter tractable algorithm for computing Pareto-optimal reconciliations and recording all events that arise in those reconciliations, along with their frequencies. We apply this method to a case study of 16 fungi to systematically characterize the complexity of MPR space across event costs and identify events supported across this space. Conclusion This work provides a new framework for studying the relationship between event costs and reconciliations that incorporates both macro-evolutionary events and population effects and is thus broadly applicable across eukaryotic species. |
| first_indexed | 2024-12-14T05:31:32Z |
| format | Article |
| id | doaj.art-6b7ef9cdaacb487eaa1a56b9ad1927fb |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-12-14T05:31:32Z |
| publishDate | 2019-12-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-6b7ef9cdaacb487eaa1a56b9ad1927fb2022-12-21T23:15:20ZengBMCBMC Bioinformatics1471-21052019-12-0120S2011310.1186/s12859-019-3206-6Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence modelRoss Mawhorter0Nuo Liu1Ran Libeskind-Hadas2Yi-Chieh Wu3Department of Computer Science, Harvey Mudd CollegeDepartment of Computer Science, Harvey Mudd CollegeDepartment of Computer Science, Harvey Mudd CollegeDepartment of Computer Science, Harvey Mudd CollegeAbstract Background Reconciliation methods are widely used to explain incongruence between a gene tree and species tree. However, the common approach of inferring maximum parsimony reconciliations (MPRs) relies on user-defined costs for each type of event, which can be difficult to estimate. Prior work has explored the relationship between event costs and maximum parsimony reconciliations in the duplication-loss and duplication-transfer-loss models, but no studies have addressed this relationship in the more complicated duplication-loss-coalescence model. Results We provide a fixed-parameter tractable algorithm for computing Pareto-optimal reconciliations and recording all events that arise in those reconciliations, along with their frequencies. We apply this method to a case study of 16 fungi to systematically characterize the complexity of MPR space across event costs and identify events supported across this space. Conclusion This work provides a new framework for studying the relationship between event costs and reconciliations that incorporates both macro-evolutionary events and population effects and is thus broadly applicable across eukaryotic species.https://doi.org/10.1186/s12859-019-3206-6PhylogeneticsReconciliationCoalescenceIncomplete lineage sortingGene duplication and lossPareto optimality |
| spellingShingle | Ross Mawhorter Nuo Liu Ran Libeskind-Hadas Yi-Chieh Wu Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model BMC Bioinformatics Phylogenetics Reconciliation Coalescence Incomplete lineage sorting Gene duplication and loss Pareto optimality |
| title | Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model |
| title_full | Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model |
| title_fullStr | Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model |
| title_full_unstemmed | Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model |
| title_short | Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model |
| title_sort | inferring pareto optimal reconciliations across multiple event costs under the duplication loss coalescence model |
| topic | Phylogenetics Reconciliation Coalescence Incomplete lineage sorting Gene duplication and loss Pareto optimality |
| url | https://doi.org/10.1186/s12859-019-3206-6 |
| work_keys_str_mv | AT rossmawhorter inferringparetooptimalreconciliationsacrossmultipleeventcostsundertheduplicationlosscoalescencemodel AT nuoliu inferringparetooptimalreconciliationsacrossmultipleeventcostsundertheduplicationlosscoalescencemodel AT ranlibeskindhadas inferringparetooptimalreconciliationsacrossmultipleeventcostsundertheduplicationlosscoalescencemodel AT yichiehwu inferringparetooptimalreconciliationsacrossmultipleeventcostsundertheduplicationlosscoalescencemodel |