Consensus of All Solutions for Intractable Phylogenetic Tree Inference.

Area of Science:

• Phylogenetics
• Computational Biology
• Bioinformatics

Background:

• Median tree problems are crucial for inferring species trees from discordant gene trees.
• Existing heuristics for NP-hard median tree problems lack provable correctness and precision.
• Current exact dynamic programming methods compute few optimal species trees, hindering analysis of all solutions.

Purpose of the Study:

• To develop an algorithmic modification for dynamic programming to compute cluster counts of all optimal species trees.
• To enable efficient computation of various consensus trees from all optimal solutions.
• To enhance phylogenetic analyses requiring comprehensive examination of optimal tree solutions.

Main Methods:

• A significant algorithmic modification of existing dynamic programming formulations.
• Computation of cluster counts for all optimal species trees.
• Development of a parallel implementation of the modified dynamic programming formulation.

Main Results:

• The modified dynamic programming formulation efficiently computes cluster counts of all optimal species trees.
• The parallel implementation demonstrates superior efficiency compared to previous methods.
• The approach successfully identified novel reassorted influenza A viruses in experimental studies.

Conclusions:

• The modified dynamic programming approach overcomes limitations in analyzing all optimal species trees.
• The parallel implementation offers a more efficient and scalable solution for phylogenetic inference.
• This method has potential applications in identifying novel viruses and enhancing pandemic preparedness.