Reconciliation with non-binary species trees.

Area of Science:

• Computational Biology
• Phylogenetics
• Evolutionary Genomics

Background:

• Gene tree reconciliation analyzes topological incongruence between gene and species trees to infer gene family evolution.
• Existing reconciliation algorithms are limited to binary species trees, overestimating duplications with non-binary trees.
• Non-binary species trees are common, with 64% of NCBI taxonomy branch points having multiple children.

Purpose of the Study:

• To develop the first algorithms for reconciling binary gene trees with non-binary species trees.
• To accurately infer gene duplications and losses, avoiding overestimation caused by incomplete lineage sorting.
• To provide efficient computational methods for evolutionary analysis.

Main Methods:

• Developed algorithms for reconciliation using an efficient mapping from gene to species trees.
• Implemented a dynamic programming algorithm to minimize duplications and losses.
• Designed a heuristic algorithm for polynomial-time estimation of minimal losses.

Main Results:

• The primary algorithm infers minimum duplications in O(|V(G)| x (k(S) + h(S))) time.
• The dynamic programming algorithm minimizes losses, performing well for polytomies with outdegree ≤ 12.
• The heuristic algorithm achieves 99% accuracy in finding optimal loss histories.

Conclusions:

• These novel algorithms provide accurate reconciliation for non-binary species trees, crucial for evolutionary studies.
• The implementation in NOTUNG facilitates both exploratory and high-throughput analysis.
• The methods enhance biological applications like ortholog identification and gene duplication time estimation.