Accurate Reconstruction for DNA Sequencing by Hybridization Based on a Constructive Heuristic

作者：Chen Yang^*; Hu Jinglu

来源：IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011, 8(4): 1134-1140.

DOI：10.1109/TCBB.2010.89

• DNA sequencing
• sequencing by hybridization
• heuristic algorithm
• bioinformatics
• microarrays

Sequencing by hybridization is a promising cost-effective technology for high-throughput DNA sequencing via microarray chips. However, due to the effects of spectrum errors rooted in experimental conditions, an accurate and fast reconstruction of original sequences has become a challenging problem. In the last decade, a variety of analyses and designs have been tried to overcome this problem, where different strategies have different trade-offs in speed and accuracy. Motivated by the idea that the errors could be identified by analyzing the interrelation of spectrum elements, this paper presents a constructive heuristic algorithm, featuring an accurate reconstruction guided by a set of well-defined criteria and rules. Instead of directly reconstructing the original sequence, the new algorithm first builds several accurate short fragments, which are then carefully assembled into a whole sequence. The experiments on benchmark instance sets demonstrate that the proposed method can reconstruct long DNA sequences with higher accuracy than current approaches in the literature.

• 出版日期2011-8