Gohardani Saeed Alirezanejad, Bagherian Mehri, Vaziri Hamidreza
Department of Applied Mathematics, Faculty of Mathematical Science, University of Guilan, Rasht, Iran.
Department of Biology, Faculty of Science, University of Guilan, Rasht, Iran.
Math Biosci Eng. 2019 Feb 26;16(3):1575-1596. doi: 10.3934/mbe.2019075.
Motif discovery problem (MDP) is one of the well-known problems in biology which tries to find the transcription factor binding site (TFBS) in DNA sequences. In one aspect, there is not enough biological knowledge on motif sites and on the other side, the problem is NP-hard. Thus, there is not an efficient procedure capable of finding motifs in every dataset. Some algorithms use exhaustive search, which is very time-consuming for large-scale datasets. On the other side, metaheuristic procedures seem to be a good selection for finding a motif quickly that at least has some acceptable biological properties. Most of the previous methods model the problem as a single objective optimization problem; however, considering multi-objectives for modeling the problem leads to improvements in the quality of obtained motifs. Some multi-objective optimization models for MDP have tried to maximize three objectives simultaneously: Motif length, support, and similarity. In this study, the multi-objective Imperialist Competition Algorithm (ICA) is adopted for this problem as an approximation algorithm. ICA is able to simulate more exploration along the solution space, so avoids trapping into local optima. So, it promises to obtain good solutions in a reasonable time. Experimental results show that our method produces good solutions compared to well-known algorithms in the literature, according to computational and biological indicators.
基序发现问题（MDP）是生物学中著名的问题之一，旨在在DNA序列中寻找转录因子结合位点（TFBS）。一方面，关于基序位点的生物学知识不足，另一方面，该问题是NP难问题。因此，不存在一种能够在每个数据集中找到基序的有效程序。一些算法使用穷举搜索，这对于大规模数据集来说非常耗时。另一方面，元启发式程序似乎是快速找到至少具有一些可接受生物学特性的基序的不错选择。以前的大多数方法将该问题建模为单目标优化问题；然而，考虑多目标来对问题进行建模会提高所获得基序的质量。一些用于MDP的多目标优化模型试图同时最大化三个目标：基序长度、支持度和相似度。在本研究中，采用多目标帝国主义竞争算法（ICA）作为该问题的近似算法。ICA能够在解空间中模拟更多的探索，因此避免陷入局部最优。所以，它有望在合理的时间内获得良好的解。实验结果表明，根据计算指标和生物学指标，与文献中著名的算法相比，我们的方法产生了良好的解。
