The novel ant colony system for DNA sequencing by hybridization

摘要

DNA sequencing by hybridization (SBH) has been a very challenging problem in computational biology. We propose a novel ant colony system through a detailed analysis of SBH. Firstly, the SBH problem is subtly transformed into a selective asymmetric traveling salesman problem with constraint condition. Then, the local mutation and neighborhood searching technique are introduced to improve the solution quality and accelerate the convergence according to the characteristic of SBH. Finally, the optimal DNA sequence is obtained by using an effective results-post-processing technique. Experimental results from extensive simulations confirm that our proposed method is significantly superior to the state-of-the-art methods in accuracy and stability.