Multiobjective Variable Neighborhood Search for Solving the Motif Discovery Problem Author(s): David L. González-Álvarez, Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Juan M. Sánchez-Pérez Keywords: Multiobjective Skewed Variable Neighborhood Search (MO–SVNS), Motif Discovery Problem (MDP), hypervolume indicator.
Abstract:
In this work we approach the Motif Discovery Problem (MDP) by using a trajectory-based heuristic. Identifying common patterns, motifs, in deoxyribonucleic 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.
The need to discover subjects/motifs that are patterns in strings isn’t limited to deoxyribonucleic acid (DNA) sequences.
A large amount of work has gone into pattern matching in bioinformatics and topic map authors should take advantage of it.