Progressive tree neighborhood applied to the maximum parsimony problem

Area of Science:

• Computational Biology
• Bioinformatics
• Evolutionary Biology

Background:

• The Maximum Parsimony (MP) problem is crucial for reconstructing phylogenetic trees from DNA sequences.
• Solving the NP-complete MP problem often involves heuristic methods and local search algorithms.
• Existing neighborhood search methods like NNI, SPR, and TBR have limitations.

Purpose of the Study:

• To analyze the influence of neighborhood relations on Maximum Parsimony heuristic methods.
• To introduce and evaluate a new Progressive Neighborhood (PN) approach for MP problem-solving.
• To compare the efficiency and robustness of PN against traditional neighborhood methods.

Main Methods:

• Analysis of Nearest Neighbor Interchange (NNI), Subtree Pruning Regrafting (SPR), and Tree-Bisection-Reconnection (TBR) neighborhoods.
• Development and implementation of the Progressive Neighborhood (PN) concept.
• Empirical evaluation using a descent algorithm applied to the Maximum Parsimony problem.

Main Results:

• The Progressive Neighborhood (PN) approach was found to be more efficient than classic neighborhoods.
• PN demonstrated greater robustness in solving the Maximum Parsimony problem.
• The method allows for finding better phylogenetic tree solutions with fewer iterations.

Conclusions:

• Progressive Neighborhood (PN) offers a significant advancement in heuristic methods for the Maximum Parsimony problem.
• The adaptive nature of PN enhances efficiency and solution quality in phylogenetic reconstruction.
• PN provides a more robust and effective alternative to traditional neighborhood search strategies.