Reference-point based non-dominated sorting for motif discovery
Laura Escobar-Encinas, Álvaro Rubio‐Largo, José Maria Granado-Criado · Applied Soft Computing · 2025
The discovery of biological motifs ( Motif Discovery Problem ) is a complex and significant issue in bioinformatics, for which metaheuristics are particularly well-suited. In this work, we focus on evaluating various multi-objective approaches that simultaneously optimize both the quality of discovered motifs and computational efficiency. Specifically, we examine the multi-objective evolutionary algorithm Non-Dominated Sorting Genetic Algorithm 3 (NSGA3) and propose modifications to adapt it to this problem, enhancing its convergence speed. We assess the convergence speed of NSGA3 by comparing it with other methods published in the literature, using twelve instances from four different organisms (fruit fly, Homo sapiens , mouse, and yeast). The analysis centers on the number of evaluations (objective function calculations) required by each algorithm to reach acceptable quality solutions. To achieve this, we examine the quality of the non-dominated solutions found by each algorithm throughout their execution, enabling us to determine which performs better. Additionally, we evaluate the success rates of the algorithms over 31 independent runs. Finally, we measure the biological significance of the solutions found by means of four well-known biological indicators, comparing the results with other approaches published in the literature.