Heuristics for multiobjective multiple sequence alignment.

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithmic Development

Background:

• Multiple sequence alignment is crucial in bioinformatics but current methods are parameter-dependent, potentially biasing results.
• Single parameter settings can oversimplify complex sequence similarity relationships.
• A multiobjective approach is needed to capture trade-offs between alignment scores and gap penalties.

Purpose of the Study:

• To reformulate multiple sequence alignment as a multiobjective optimization problem.
• To generate a set of diverse sequence alignments representing trade-offs between substitution scores and indel minimization.
• To provide practitioners with enhanced information for selecting the most plausible sequence alignment.

Main Methods:

• Developed heuristic approaches based on local search procedures to compute a set of sequence alignments.
• Analyzed algorithm design choices, including starting alignment and neighborhood search definitions.
• Employed a perturbation technique to enhance local search and generate a wide range of high-quality alignments.

Main Results:

• Experimental validation on BAliBASE 3.0 benchmark sequences.
• Evaluation using the hypervolume indicator to assess the quality of the generated alignment set.
• Identified effective parameter choices for the proposed multiobjective approach.

Conclusions:

• The multiobjective approach provides a more comprehensive view of sequence similarity than traditional methods.
• Experimental results demonstrate competitive or superior performance compared to established tools like TCoffee and Clustal Omega in specific metrics.
• The method offers valuable insights for practitioners in selecting appropriate sequence alignments.