Title :
A Compounded Genetic and Simulated Annealing Algorithm for the Closest String Problem
Author :
Liu, Xiaolan ; Holger, Mauch ; Hao, Zhifeng ; Wu, Guangchao
Author_Institution :
Sch. of Comput. Sci. &Eng., South China Univ. of Technol., Guangzhou
Abstract :
The closest string problem is an NP-hard problem, which arises in computational molecular biology and coding theory. Its task is to find a string that minimizes maximum Hamming distance to a given set of strings. In this paper, a compounded genetic and simulated annealing algorithm (CGSA) which combines the merits of genetic algorithms and simulated annealing is presented to solve CSP. An adapting two-point crossover operator and a heuristic gene mutation operator designed by us are used in CGSA. In addition, by analyzing the optimal solution´s structural features some rules are designed to pretreat the data, which reduces the problem size. We report computational results which show that the CGSA is capable of finding good solutions in a reasonable amount of time.
Keywords :
Hamming codes; biology computing; computational complexity; genetic algorithms; genetics; molecular biophysics; simulated annealing; Hamming distance; NP-hard problem; closest string problem; coding theory; computational molecular biology; genetic algorithm; heuristic gene mutation operator; simulated annealing algorithm; two-point crossover operator; Biological system modeling; Biology computing; Codes; Computational biology; Computational modeling; Genetic algorithms; Genetic mutations; Hamming distance; NP-hard problem; Simulated annealing;
Conference_Titel :
Bioinformatics and Biomedical Engineering, 2008. ICBBE 2008. The 2nd International Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-1-4244-1747-6
Electronic_ISBN :
978-1-4244-1748-3
DOI :
10.1109/ICBBE.2008.171
