Autumn Algorithm-Computation of Hybridization Networks for Realistic Phylogenetic Trees

Area of Science:

• Evolutionary biology
• Computational phylogenetics
• Bioinformatics

Background:

• Phylogenetic networks model evolutionary history with reticulations.
• Existing methods for minimum hybridization networks often assume simplified, idealized input trees.
• Realistic biological data present challenges like multifurcations, ambiguous rooting, and differing taxa sets.

Purpose of the Study:

• To develop a novel algorithm for computing minimum hybridization networks from "realistic" rooted phylogenetic trees.
• To explore the application of this algorithm in improving the rooting of input phylogenetic trees.
• To introduce the "autumn trees" framework for algorithm formulation using "maximum acyclic agreement forests".

Main Methods:

• Developed a new algorithm for minimum hybridization network computation tailored for realistic phylogenetic trees.
• Introduced the "autumn trees" concept for algorithm design, leveraging "maximum acyclic agreement forests".
• Implemented a parallel version of the algorithm within the open-source Dendroscope 3 software.

Main Results:

• The algorithm successfully computes minimum hybridization networks for complex, realistic phylogenetic trees.
• The computational complexity is influenced by the dissimilarity between input trees.
• The parallel implementation demonstrates practical efficiency for reasonably similar biological trees.

Conclusions:

• The new algorithm provides a robust method for constructing minimum hybridization networks from challenging biological data.
• The approach offers potential improvements for phylogenetic tree rooting.
• The Dendroscope 3 software enables biologists to explore phylogenetic networks and their evolutionary implications.