A fast tool for minimum hybridization networks.

Area of Science:

• Computational Biology
• Phylogenetics
• Evolutionary Biology

Background:

• Hybridization events in evolution can result in different phylogenetic trees for the same species set.
• Combining these trees into a hybridization network with minimal hybridization events presents computational challenges.
• Existing tools like HybridNet and Dendroscope 3 are too slow for large datasets.

Purpose of the Study:

• To develop a faster software tool for computing, constructing, and enumerating minimum hybridization networks.
• To address the performance limitations of current phylogenetic network construction software.

Main Methods:

• Developed FastHN, a software tool in ANSI C, refining HybridNet.
• Implemented preprocessing to reduce tree size or decompose problems into smaller subproblems.
• Utilized a fast rSPR distance algorithm to prune the search tree.
• Employed a strategy to select distant sibling leaves during the exhaustive search.

Main Results:

• FastHN significantly outperforms HybridNet and Dendroscope 3 in speed.
• Even for complex cases (hybridization number ~25, 100 leaves), FastHN completes within minutes.
• FastHN uses minimal memory, comparable to HybridNet, unlike the memory-intensive Dendroscope 3.
• Single-threaded FastHN is faster than multi-threaded Dendroscope 3 on multi-core PCs.

Conclusions:

• FastHN offers substantial speed improvements over existing tools for constructing phylogenetic hybridization networks.
• The performance gains are more pronounced with higher hybridization numbers.
• FastHN is a memory-efficient alternative for phylogenetic network analysis.