Journal
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
Volume 10, Issue 4, Pages 939-956Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TCBB.2013.103
Keywords
Gene tree parsimony; gene duplication; gene loss; incomplete lineage sorting; minimizing deep coalescences (MDC); phylogenomics; phylogenetics
Categories
Funding
- US National Science Foundation [0334832, 0830012]
- Direct For Biological Sciences
- Division Of Environmental Biology [0334832] Funding Source: National Science Foundation
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1017189] Funding Source: National Science Foundation
Ask authors/readers for more resources
The use of genomic data sets for phylogenetics is complicated by the fact that evolutionary processes such as gene duplication and loss, or incomplete lineage sorting (deep coalescence) cause incongruence among gene trees. One well-known approach that deals with this complication is gene tree parsimony, which, given a collection of gene trees, seeks a species tree that requires the smallest number of evolutionary events to explain the incongruence of the gene trees. However, a lack of efficient algorithms has limited the use of this approach. Here, we present efficient algorithms for SPR and TBR-based local search heuristics for gene tree parsimony under the 1) duplication, 2) loss, 3) duplication-loss, and 4) deep coalescence reconciliation costs. These novel algorithms improve upon the time complexities of previous algorithms for these problems by a factor of n, where n is the number of species in the collection of gene trees. Our algorithms provide a substantial improvement in runtime and scalability compared to previous implementations and enable large-scale gene tree parsimony analyses using any of the four reconciliation costs. Our algorithms have been implemented in the software packages DupTree and iGTP, and have already been used to perform several compelling phylogenetic studies.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available