A Memetic Algorithm for closest string problem and farthest string problem

摘要

Sequences consensus problems are especially important in studying molecular evolution, protein structures, and drug target design. In this paper, we work on two of these problems, namely closest string problem and farthest string problem. These problems are NP-hard, and none of exact algorithms already proposed to solve them is in polynomial time. Many non-exact algorithms have been proposed which try to obtain ‘good’ solutions in acceptable time for these problems. In this paper, a Memetic Algorithm (MA) is proposed for the closest string problem, which outperforms the existing algorithms. We then extend the proposed algorithm to address the farthest string problem.