A Multiobjective Variable Neighborhood Search for Solving the Motif Discovery Problem

摘要

In this work we approach the Motif Discovery Problem (MDP) by using a trajectory-based heuristic. Identifying common patterns, motifs, in deoxyribonu-cleic acid (DNA) sequences is a major problem in bioinformatics, and it has not yet been resolved in an efficient manner. The MDP aims to discover patterns that maximize three objectives: support, motif length, and similarity. Therefore, the use of multiobjective evolutionary techniques can be a good tool to get quality solutions. We have developed a multiobjective version of the Variable Neighborhood Search (MO-VNS) in order to handle this problem. After accurately tuning this algorithm, we also have implemented its variant Multiobjective Skewed Variable Neighborhood Search (MO-SVNS) to analyze which version achieves more complete solutions. Moreover, in this work, we incorporate the hypervolume indicator, allowing future comparisons of other authors. As we will see, our algorithm achieves very good solutions, surpassing other proposals.