The worst case complexity of maximum parsimony.

Area of Science:

• Computational Biology
• Bioinformatics
• Evolutionary Biology

Background:

• Constructing phylogenetic trees is a fundamental problem in computational biology.
• Maximum Parsimony (MP) is a classical optimization method for inferring evolutionary relationships from genomic sequences.
• The efficiency of MP algorithms is crucial for analyzing large datasets.

Purpose of the Study:

• To reexamine the maximum parsimony optimization problem for general (asymmetric) scoring matrices.
• To analyze and compare the worst-case performance bounds of three distinct MP approaches.
• To introduce and evaluate a new agglomerative, 'bottom-up' MP method.

Main Methods:

• Analysis of worst-case bounds for MP algorithms.
• Comparison of three MP approaches: Cavalli-Sforza and Edwards, Hendy and Penny, and a novel agglomerative method.
• Focus on rooted phylogenies implied by asymmetric scoring matrices.

Main Results:

• The Hendy and Penny approach demonstrates a speed improvement of Θ(√n) over the Cavalli-Sforza and Edwards approach.
• The newly presented agglomerative approach offers a further speed improvement of Θ(n) compared to the Cavalli-Sforza and Edwards method.
• Both analyzed approaches are computationally more efficient than the classical Cavalli-Sforza and Edwards method.

Conclusions:

• The study provides significant advancements in the computational efficiency of phylogenetic tree construction using maximum parsimony.
• The novel agglomerative method presents a faster alternative for inferring evolutionary relationships, particularly for large datasets.
• These findings contribute to more efficient sequence analysis in computational and evolutionary biology.