Hitch-hiking: a parallel heuristic search strategy, applied to the phylogeny problem

Area of Science:

• Computational Biology
• Bioinformatics
• Evolutionary Genetics

Background:

• Phylogenetic inference aims to reconstruct evolutionary relationships.
• Maximum Parsimony is a criterion for minimizing evolutionary changes on a tree.
• Heuristic search strategies are essential for complex optimization problems in phylogenetics.

Purpose of the Study:

• To introduce and evaluate a novel parallel heuristic search strategy called Hitch-hiking.
• To assess the effectiveness of Hitch-hiking in improving solutions for the artificial phylogeny problem.
• To demonstrate the general applicability of Hitch-hiking in combinatorial optimization.

Main Methods:

• Development of the Hitch-hiking parallel heuristic search strategy.
• Application of Hitch-hiking to an artificial phylogeny problem with pseudo-randomly evolved sequences.
• Comparison of solutions found with and without the Hitch-hiking strategy.
• Analysis of the strategy's ability to provide information on the problem's landscape.

Main Results:

• The Hitch-hiking strategy is robust and yields better average solutions compared to standard methods.
• The strategy effectively aids in reconstructing evolutionary trees under the Maximum Parsimony criterion.
• Hitch-hiking dynamically provides valuable information about the characteristics of the problem's search space.
• The parallelization scheme proved beneficial for improving search efficiency and solution quality.

Conclusions:

• Hitch-hiking is a valuable parallelization scheme for existing heuristic search strategies.
• The strategy demonstrates broad potential for application across various combinatorial optimization domains.
• This approach offers a significant advancement in computational methods for phylogenetic analysis and beyond.