Reconciliation with non-binary species trees

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Gene and species tree reconciliation addresses topological incongruence using gene duplication and loss events.
• Existing methods struggle with non-binary species trees, overestimating duplications by conflating them with deep coalescence.
• Non-binary species trees are common, with 64% of NCBI taxonomy branch points having multiple children.

Purpose of the Study:

• To present the first formal algorithm for reconciling binary gene trees with non-binary species trees under a duplication-loss parsimony model.
• To accurately infer the minimum number of gene duplications and losses, distinguishing them from deep coalescence.
• To implement these algorithms in a user-friendly and high-throughput software.

Main Methods:

• Developed a novel algorithm for reconciling binary gene trees with non-binary species trees.
• Utilized a space-efficient mapping between gene and species trees.
• Achieved a time complexity of O(|V(G)| . (k(S) + h(S))) for inferring duplications and losses.
• Introduced a dynamic programming algorithm for a combined loss model.

Main Results:

• The algorithm accurately infers the minimum number of duplications and losses when reconciling gene trees with non-binary species trees.
• The computational efficiency is dependent on the gene tree size and species tree width and height.
• A combined loss model was developed to account for losses in sibling species.

Conclusions:

• This work provides the first accurate method for reconciling gene trees with non-binary species trees.
• The developed algorithms are implemented in the NOTUNG software, supporting both interactive and automated analyses.
• Accurate reconciliation is vital for downstream biological applications like ortholog identification and evolutionary analysis.