Consensus properties for the deep coalescence problem and their application for scalable tree search.

Area of Science:

• Phylogenetics
• Computational Biology
• Evolutionary Biology

Background:

• Phylogenetic inference methods face challenges from biological processes like deep coalescence (incomplete lineage sorting).
• Deep coalescence causes incongruence between gene trees and the species tree.
• The deep coalescence problem seeks a species tree minimizing deep coalescence events, but its properties and scalability were unclear.

Purpose of the Study:

• To investigate the consensus properties of the deep coalescence problem.
• To develop a computationally efficient method for phylogenetic inference that accounts for deep coalescence.
• To ensure phylogenetic solutions satisfy desirable properties like the Pareto property.

Main Methods:

• Proved that the deep coalescence consensus tree problem satisfies the Pareto property for clusters (clades).
• Introduced a novel divide and conquer algorithm for the deep coalescence problem, leveraging the Pareto property.
• The method refines the strict consensus of input gene trees to reduce computational complexity.

Main Results:

• Demonstrated that consensus clusters present in all input gene trees are found in every optimal solution.
• The divide and conquer method significantly reduces the complexity of tree search in practice.
• Guaranteed that the estimated species tree satisfies the Pareto property.

Conclusions:

• The divide and conquer method substantially improves the speed of phylogenetic analyses compared to heuristics ignoring the Pareto property.
• This new method guarantees solutions adhere to the Pareto consensus property.
• The approach extends the applicability of the deep coalescence problem to very large datasets with numerous taxa.