Abstract: An improved Max-Min Ant algorithm is designed based on the characteristics of DNA sequencing by hybridization. First, a preparatory treatment is done to transform the problem into a non -symmetrical traveling salesman problem with constraints. Second, after improving the state transition rule and the global update policy, a simple and efficient local search technique is designed by applying the idea of variable neighborhood search. Finally, the post processing technology is adopted to solve the problem of length restraint. The result shows that our algorithm is significantly better than other algorithms in raising the accuracy and stability of solving DNA sequencing by hybridization.