Revisiting Motif Finding: Do Bi-objective Metaheuristics Surpass Single-objective Metaheuristics?

Abstract Background: The discovery of DNA motifs is essential for studying gene expression and function in many biological systems. Most existing algorithms for motif detection rely on a single optimization criterion or objective function. This study formulates motif finding as a bi-objective optimization problem and investigates whether multi-objective metaheuristics offer potential advantages over single-objective approaches. Results: We developed four variants of the Non-dominated Sorting Genetic Algorithm II (NSGAII) incorporating simple, problem-specific genetic operators. Experiments on six benchmark datasets from three organisms demonstrate that our bi-objective approach significantly outperforms the state-of-the-art Artificial Bee Colony (ABC) metaheuristic. Remarkably, NSGAII-PMC achieved superior performance over ABC using 6 times fewer fitness evaluations, highlighting its computational efficiency. The synergistic combination of problem-specific operators proved essential, with individual operators showing limited effectiveness compared to their joint application. Conclusions: Our findings question the common belief that single-objective metaheuristics are better suited for combinatorial problems like motif finding. The bi-objective formulation helps maintain diversity and avoid premature convergence, even with partially correlated objectives, leading to better solutions than dedicated single-objective optimization. Simple, interpretable problem-specific adaptations can yield substantial performance gains over sophisticated alternatives. These results suggest that bi-objective approaches may provide more robust and computationally efficient solutions for DNA motif discovery, opening new research directions in bioinformatics.