A metaheuristic approach for the sequencing by hybridization problem with positive and negative errors

This work introduces a metaheuristic method for the reconstruction of the DNA string from its l-mer content in the presence of large amounts of positive and negative errors. The procedure consists of three parts: the formulation of the problem as an asymmetric traveling salesman problem (ATSP), a technique for handling the positive errors and an optimization algorithm that solves the formulated problem. The optimization algorithm is a variation of the threshold accepting method with intense local search and its function is controlled by a size diminishing shell. The optimization algorithm is used consecutively on ATSPs of continuously decreasing sizes till it reaches a final solution. The proposed method provides solutions of better quality compared to algorithms in the recent bibliography.