Accurate reconstruction for DNA sequencing by hybridization based on a constructive heuristic

Yang Chen*, Jinglu Hu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Article number5582074
Pages (from-to)1134-1140
Number of pages7
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number4
Publication statusPublished - 2011


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

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Applied Mathematics


Dive into the research topics of 'Accurate reconstruction for DNA sequencing by hybridization based on a constructive heuristic'. Together they form a unique fingerprint.

Cite this