2014 | OriginalPaper | Chapter
Reconciliation with Non-binary Gene Trees Revisited
Authors : Yu Zheng, Louxin Zhang
Published in: Research in Computational Molecular Biology
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
By reconciling the phylogenetic tree of a gene family with the corresponding species tree, it is possible to infer lineage-specific duplications and losses with high confidence and hence annotate orthologs and paralogs. However, the currently available reconciliation methods for non-binary gene trees are computationally expensive for being applied on a genomic level. Here, an
O
(|
G
| + |
S
|) algorithm is presented to reconcile an arbitrary gene tree
G
with its corresponding species tree
S
, where |·| denotes the number of nodes in the corresponding tree. The improvement is achieved through two innovations: a fast computation of compressed child-image subtrees and efficient reconstruction of irreducible duplication histories.