A hyper-heuristic approach to sequencing by hybridization of DNA sequences

Citation

Blazewicz J, Burke E, Kendall G, Mruczkiewicz W, Oguz C & Swiercz A (2013) A hyper-heuristic approach to sequencing by hybridization of DNA sequences. Annals of Operations Research, 207 (1), pp. 27-41. https://doi.org/10.1007/s10479-011-0927-y

Abstract
In this paper we investigate the use of hyper-heuristic methodologies for predicting DNA sequences. In particular, we utilize Sequencing by Hybridization. We believe that this is the first time that hyper-heuristics have been investigated in this domain. A hyper-heuristic is provided with a set of low-level heuristics and the aim is to decide which heuristic to call at each decision point. We investigate three types of hyper-heuristics. Two of these (simulated annealing and tabu search) draw their inspiration from meta-heuristics. The choice function hyper-heuristic draws its inspiration from reinforcement learning. We utilize two independent sets of low-level heuristics. The first set is based on a previous tabu search method, with the second set being a significant extension to this basic set, including utilizing a different representation and introducing the definition of clusters. The datasets we use comprises two randomly generated datasets and also a publicly available biological dataset. In total, we carried out experiments using 70 different combinations of heuristics, using the three datasets mentioned above and investigating six different hyper-heuristic algorithms. Our results demonstrate the effectiveness of a hyper-heuristic approach to this problem domain. It is necessary to provide a good set of low-level heuristics, which are able to both intensify and diversify the search but this approach has demonstrated very encouraging results on this extremely difficult and important problem domain.

Keywords
Hyper-heuristics; Simulated annealing; Tabu search; Choice function; Sequencing by hybridization

Journal
Annals of Operations Research: Volume 207, Issue 1