Revisiting motif finding: do bi-objective metaheuristics surpass single-objective metaheuristics?

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• DNA motif discovery is crucial for understanding gene expression and function.
• Current algorithms often use a single optimization criterion, potentially limiting performance.
• This study explores a novel bi-objective optimization framework for motif finding.

Purpose of the Study:

• To investigate the potential advantages of multi-objective metaheuristics for DNA motif discovery.
• To compare a bi-objective approach against state-of-the-art single-objective methods.
• To assess the impact of problem-specific genetic operators within a multi-objective framework.

Main Methods:

• Developed four variants of the Non-dominated Sorting Genetic Algorithm II (NSGA-II).
• Incorporated simple, problem-specific genetic operators into the NSGA-II algorithm.
• Evaluated performance on six benchmark datasets from three different organisms.

Main Results:

• The bi-objective NSGA-II variants significantly outperformed the Artificial Bee Colony (ABC) metaheuristic.
• NSGA-II-PMC demonstrated superior performance with 6x fewer fitness evaluations than ABC.
• The synergistic combination of problem-specific operators was critical for performance gains.

Conclusions:

• Bi-objective optimization challenges the notion that single-objective methods are superior for combinatorial problems like motif finding.
• The bi-objective approach enhances solution diversity and prevents premature convergence.
• Simple, tailored adaptations can outperform complex alternatives, suggesting new avenues for robust and efficient DNA motif discovery.