2014 | OriginalPaper | Buchkapitel
Reconciliation with Non-binary Gene Trees Revisited
verfasst von : Yu Zheng, Louxin Zhang
Erschienen in: Research in Computational Molecular Biology
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.