Accurate reconstruction for DNA sequencing by hybridization based on a constructive heuristic.
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.
Chen
Yang
Y
Furuzuki Laboratory, Graduate School of Information, Production and Systems, Waseda University, N259, 2-7 Hibikino, Wakamatsu-ku, Kitakyushu-shi, Fukuoka 808-0135, Japan. yangchen@ruri.waseda.jp
Hu
Jinglu
J
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D006801:Humans; D008957:Models, Genetic; D009693:Nucleic Acid Hybridization / Q000379:methods*; D020411:Oligonucleotide Array Sequence Analysis; D017422:Sequence Analysis, DNA / Q000379:methods*