Embedding gene trees into phylogenetic networks by conflict resolution algorithms

Area of Science:

• Evolutionary biology
• Computational phylogenetics
• Bioinformatics

Background:

• Phylogenetic networks model evolutionary processes with reticulate events (hybridization, recombination, HGT).
• Displayed trees are derived from networks by removing reticulation edges.
• Displayed trees can represent gene family evolution shaped by reticulations.

Purpose of the Study:

• To develop algorithms for inferring optimal displayed trees from gene trees and tree-child networks.
• To compute lower bounds for displayed tree costs under deep coalescence and duplication costs.
• To provide methods for verifying exact solutions and resolving conflicting reticulation edges.

Main Methods:

• A dynamic programming (DP) algorithm with O(mn) time complexity for computing lower bounds.
• A conflict resolution algorithm utilizing DP invocations.
• Algorithms for level-k tree-child networks and branch and bound solutions.
• Extension of algorithms to broader classes of phylogenetic networks.

Main Results:

• An O(mn) DP algorithm computes a lower bound for optimal displayed tree cost and verifies exactness.
• A conflict resolution algorithm is proposed, requiring O(r) DP calls.
• Efficient algorithms for level-k networks and branch and bound solutions are presented.
• Simulated data shows average runtimes of O(mn) for deep coalescence and O(mn) for duplication costs.

Conclusions:

• Algorithms perform well on empirical and simulated data, outperforming enumeration strategies.
• Efficiently resolve internal dissimilarities between gene trees and networks.
• Enable analysis of complex phylogenetic networks with numerous reticulations.