Bounding the Softwired Parsimony Score of a Phylogenetic Network

Area of Science:

• Evolutionary Biology
• Computational Biology
• Bioinformatics

Background:

• Phylogenetic trees struggle to represent complex evolutionary histories involving reticulation events like hybridization.
• Phylogenetic networks offer a more suitable framework for depicting such intricate evolutionary pasts.
• Reconstructing phylogenetic networks is computationally challenging due to their complex structures.

Purpose of the Study:

• To investigate the maximum difference between parsimony scores of phylogenetic trees within a network and the network's own parsimony score.
• To establish bounds for this score difference in phylogenetic networks, specifically under softwired parsimony.
• To analyze the behavior of these bounds for semi-directed networks and contrast with parental parsimony.

Main Methods:

• Utilizing the concept of an 'informative blob' for analysis.
• Applying methods to rooted binary level-k phylogenetic networks with gap-free sequence alignments.
• Developing theoretical bounds for parsimony score differences.

Main Results:

• A bound is established for the difference between the parsimony score of any contained phylogenetic tree and the network's softwired parsimony score.
• This bound is shown to be independent of sequence alignment length and the number of character states.
• An analogous bound is found for semi-directed networks, but not for parental parsimony.

Conclusions:

• The study provides a theoretical bound for parsimony score differences in phylogenetic networks, aiding computational efficiency.
• The findings highlight the distinct properties of softwired versus parental parsimony in network reconstruction.
• The introduced 'informative blob' concept offers a novel tool for analyzing phylogenetic networks.