Meta-heuristic algorithms and experimental analysis for the unique restriction site placement problem

Abstract

Genome synthesis has become an important tool in many fields of recombinant DNA technology including vaccine development, gene therapy and molecular engineering. There had been a number of researches that investigated the function of genes in a sequence and how to synthesize genome sequence according to user specification. The purpose of this study is to find a genome sequence which provides maximum amount of flexibility and independence to biologists to run experiment with the sequence. Restriction enzymes are reagents widely used by molecular biologists for genetic manipulation and analysis. The decision version of Unique Restriction Site Placement Problem (URSPP) has been proved to be NP complete. Since URSPP is a multi-objective optimization problem and multi-objective optimization often shows good performance through elitist approach, our target is to introduce elitism in different meta-heuristic strategies to solve URSPP. Additionally, we change one of the objectives of URSPP to make the problem biologically more interesting and meaningful. We carry out extensive experiments considering different clinically important viruses as well as large viral sequences considering existing meta-heuristic algorithms in the literature as well as our newly developed algorithms. Our experimental results show that our approaches give better results than traditional meta-heuristics. As a result, we provide a software tool according to our approach which would be helpful for genome synthesis from biological viewpoint.