Inferring duplication episodes from unrooted gene trees
Abstract Background One of evolutionary molecular biology fundamental issues is to discover genomic duplication events and their correspondence to the species tree. Such events can be reconstructed by clustering single gene duplications inferred by reconciling a set of gene trees with a species tree...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2018-05-01
|
| Series: | BMC Genomics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12864-018-4623-z |
| _version_ | 1818138315899011072 |
|---|---|
| author | Jarosław Paszek Paweł Górecki |
| author_facet | Jarosław Paszek Paweł Górecki |
| author_sort | Jarosław Paszek |
| collection | DOAJ |
| description | Abstract Background One of evolutionary molecular biology fundamental issues is to discover genomic duplication events and their correspondence to the species tree. Such events can be reconstructed by clustering single gene duplications inferred by reconciling a set of gene trees with a species tree. Results Here we propose the first solutions to the genomic duplication problem in which every reconciliation with the minimal number of single gene duplications is allowed and the method of clustering called minimum episodes under the assumption that input gene trees are unrooted. Conclusions We showed new theoretical properties of unrooted reconciliation for the duplication cost and apply them to design several exact and heuristic algorithms for solving the problem. Our evaluation study on empirical dataset confirmed several genomic duplication events from the literature and demonstrate that algorithms can be successfully applied. |
| first_indexed | 2024-12-11T10:10:15Z |
| format | Article |
| id | doaj.art-7ed31f373ac44cabb4db63715230b284 |
| institution | Directory Open Access Journal |
| issn | 1471-2164 |
| language | English |
| last_indexed | 2024-12-11T10:10:15Z |
| publishDate | 2018-05-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Genomics |
| spelling | doaj.art-7ed31f373ac44cabb4db63715230b2842022-12-22T01:11:46ZengBMCBMC Genomics1471-21642018-05-0119S5718310.1186/s12864-018-4623-zInferring duplication episodes from unrooted gene treesJarosław Paszek0Paweł Górecki1Warsaw University, Faculty of Mathematics, Informatics and MechanicsWarsaw University, Faculty of Mathematics, Informatics and MechanicsAbstract Background One of evolutionary molecular biology fundamental issues is to discover genomic duplication events and their correspondence to the species tree. Such events can be reconstructed by clustering single gene duplications inferred by reconciling a set of gene trees with a species tree. Results Here we propose the first solutions to the genomic duplication problem in which every reconciliation with the minimal number of single gene duplications is allowed and the method of clustering called minimum episodes under the assumption that input gene trees are unrooted. Conclusions We showed new theoretical properties of unrooted reconciliation for the duplication cost and apply them to design several exact and heuristic algorithms for solving the problem. Our evaluation study on empirical dataset confirmed several genomic duplication events from the literature and demonstrate that algorithms can be successfully applied.http://link.springer.com/article/10.1186/s12864-018-4623-zGenomic duplicationDuplication episodeMinimum episodes problemReconciliationUnrooted gene treeSpecies tree |
| spellingShingle | Jarosław Paszek Paweł Górecki Inferring duplication episodes from unrooted gene trees BMC Genomics Genomic duplication Duplication episode Minimum episodes problem Reconciliation Unrooted gene tree Species tree |
| title | Inferring duplication episodes from unrooted gene trees |
| title_full | Inferring duplication episodes from unrooted gene trees |
| title_fullStr | Inferring duplication episodes from unrooted gene trees |
| title_full_unstemmed | Inferring duplication episodes from unrooted gene trees |
| title_short | Inferring duplication episodes from unrooted gene trees |
| title_sort | inferring duplication episodes from unrooted gene trees |
| topic | Genomic duplication Duplication episode Minimum episodes problem Reconciliation Unrooted gene tree Species tree |
| url | http://link.springer.com/article/10.1186/s12864-018-4623-z |
| work_keys_str_mv | AT jarosławpaszek inferringduplicationepisodesfromunrootedgenetrees AT pawełgorecki inferringduplicationepisodesfromunrootedgenetrees |