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 (NSGA-II) 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, NSGA-II-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, resulting in better solutions than those obtained through 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.

Keywords: Bioinformatics; Metaheuristics; Motif finding; Multi-objective optimization.

Fig. 1

Alignment of substrings from three DNA sequences

Fig. 2

Solution encoding scheme illustrated with a toy example of sequences of length and motif length . A candidate solution (left) is represented as an integer vector (right), where each entry specifies the 0-based starting index of the motif in the corresponding sequence. The highlighted motif instances (shown in red) begin at positions 2, 5, 3, and 4 in sequences , , , and , respectively

Fig. 3

Comparison among baseline NSGA-II and its 3 variants based on hypervolume (higher is better) on six datasets. In each plot, the horizontal axis represents the four motif lengths (), while the vertical axis depicts the corresponding hypervolume values. The boxplots illustrate the distribution of the final hypervolume values across 20 independent runs for each algorithm on each dataset

Fig. 4

Similarity score (higher is better) achieved by ABC-S (ABC [7] with similarity as the objective), and the NSGA-II variants on six datasets. In each plot, the horizontal axis represents the four motif lengths (), while the vertical axis depicts the corresponding similarity values. The boxplots illustrate the distribution of the best similarity scores across 20 independent runs for each algorithm on each dataset

Fig. 5

Entropy score (higher is better) achieved by ABC-E (ABC [7] with entropy as the objective), the NSGA-II variants on six datasets. In each plot, the horizontal axis represents the four motif lengths (), while the vertical axis depicts the corresponding entropy values. The boxplots illustrate the distribution of the best entropy scores across 20 independent runs for each algorithm on each dataset

Fig. 6

The Pareto solutions obtained by different algorithms accumulated over 20 independent runs on three datasets (hm03, hm09g, and yst04r). Each column represents a dataset, with the four motif lengths (16, 18, 20, and 22) arranged vertically across rows. Each plot visualizes the non-dominated solutions in the 2D objective space for each dataset and motif length. The points are color-coded based on the algorithm that generated them (NSGA-II, NSGA-II-PC, NSGA-II-PM, NSGA-II-PMC, ABC-S, and ABC-E)

Fig. 7

The Pareto solutions obtained by different algorithms accumulated over 20 independent runs on three datasets (yst08r, dm01g, and dm03g). Each column represents a dataset, with the four motif lengths (16, 18, 20, and 22) arranged vertically across rows. Each plot visualizes the non-dominated solutions in the 2D objective space for each dataset and motif length. The points are color-coded based on the algorithm that generated them (NSGA-II, NSGA-II-PC, NSGA-II-PM, NSGA-II-PMC, ABC-S, and ABC-E)

Fig. 8

Sensitivity analysis of mutation rate () and crossover rate () for three representative instances. The top row corresponds to hm09g (), the middle row to yst08r (), and the bottom row to dm01g (). For each instance, we report average hypervolume (leftmost column), similarity (middle column), and entropy (rightmost column) values over 10 independent runs across all combinations. Darker colors indicate better performance