A program to compute the soft Robinson-Foulds distance between phylogenetic networks

Area of Science:

• Computational evolutionary biology
• Bioinformatics
• Genomics

Background:

• Phylogenetic networks model reticulate evolutionary events, crucial for understanding evolutionary history.
• Reconstruction and comparison of phylogenetic networks rely on understanding relationships with trees and clusters.
• Key challenges include the NP-complete tree and cluster containment problems in phylogenetic networks.

Purpose of the Study:

• To develop efficient computational methods for analyzing phylogenetic networks.
• To facilitate the reconstruction and validation of phylogenetic network models.
• To compute the Soft Robinson-Foulds distance between phylogenetic networks.

Main Methods:

• Developed a fast exponential-time algorithm for the cluster containment problem on arbitrary networks.
• Implemented the algorithm in C, extending it to compute the Soft Robinson-Foulds distance.
• Conducted simulation tests to evaluate the performance and applicability of the developed programs.

Main Results:

• A C program was developed for fast computation of the Soft Robinson-Foulds distance.
• The developed algorithms and programs are demonstrated to be fast enough for practical use.
• Simulation data suggests the distribution of the Soft Robinson-Foulds distance between networks is unlikely to be normal.

Conclusions:

• Two computer programs facilitate reconstruction and validation of phylogenetic network models.
• The developed tools are efficient for practical applications in evolutionary and comparative genomics.
• The study provides insights into the statistical properties of phylogenetic network distances.