A hybrid algorithm for the DNA sequencing problem

We present a hybrid algorithm, which may be seen as an approach within the recently introduced area of matheuristics, i.e., an approach in which mathematical programming techniques and metaheuristic schemes are effectively intertwined. The algorithm is tested on 400 benchmark instances from the literature and compares favorably with the best known algorithm. In addition, an explanation concerning the relation between error distribution and algorithmic performance is provided, illustrating that the way in which negative errors are distributed within the spectrum has a bearing on the overall algorithmic performance.