Genetic algorithm for large-scale maximum parsimony phylogenetic analysis of proteins

Area of Science:

• Computational Biology
• Bioinformatics
• Evolutionary Biology

Background:

• Phylogenetic tree inference is computationally intensive, with a vast number of possible trees even for small datasets.
• Heuristic methods are crucial for efficiently searching optimal phylogenetic trees and reducing computation time.

Purpose of the Study:

• To develop and validate a novel heuristic approach for phylogenetic inference.
• To reduce the computational time required for weighted maximum parsimony (WMP) phylogenetic inference, particularly for large datasets.

Main Methods:

• Implementation of a genetic algorithm (GA) for heuristic searching in phylogenetic inference.
• Application of a weighted maximum parsimony criterion using amino acid sequences.
• Validation of the GA parameters and the WMP criterion using an artificial dataset and comparison with other phylogenetic methods.

Main Results:

• The genetic algorithm approach significantly reduces the time for weighted maximum parsimony phylogenetic inference.
• This method enables the construction of phylogenetic trees for datasets with over 200 taxa in practical time on a standard personal computer.
• It is the first implementation of a weighted maximum parsimony criterion specifically for amino acid sequences.

Conclusions:

• Genetic algorithms provide an effective heuristic strategy for complex phylogenetic inference problems.
• The developed WMP method with GA optimization is efficient and scalable for large-scale phylogenetic analyses.
• This approach enhances the feasibility of constructing large phylogenetic trees, advancing evolutionary studies.