Accelerating dna sequencing-by-hybridization with noise

Chen Chen, Dong Xin, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

As a potential alternative to current wet-lab technologies, DNA sequencing-by-hybridization (SBH) has received much attention from different research communities. In order to deal with real applications, experiment environments should not be considered as error-free. Previously, under the assumption of random independent hybridization errors, Leong et, al. [9 J presented an algorithm for sequence reconstruction which exhibits graceful degradation of output accuracy as the error rate increases. However, as the authors also admitted, a notable downside of their method is its too high computational cost. In this paper, we show that the poor efficiency of [9] is due to its mixing-up of situations with widely different characteristics and treating everything in the safest but also slowest way. Our new algorithm addresses this problem and pushes analysis down to a finer level where a more effective solution is proposed. As demonstrated by experimentations on real human genome datasets, this new methodology yields significant performance improvements and at the same time guarantees almost the same degree of output accuracy.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th International Workshop on Bioinformatics, BIOKDD 2005
Pages29-36
Number of pages8
DOIs
StatePublished - Dec 1 2005
Event5th International Workshop on Bioinformatics, BIOKDD 2005 - In Conjunction with 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2005 - Chicago, IL, United States
Duration: Aug 21 2005Aug 21 2005

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

Other5th International Workshop on Bioinformatics, BIOKDD 2005 - In Conjunction with 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2005
CountryUnited States
CityChicago, IL
Period8/21/058/21/05

Keywords

  • Algorithmic efficiency
  • Clues from the genome
  • Noise
  • Sequencing-by-hybridization

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Accelerating dna sequencing-by-hybridization with noise'. Together they form a unique fingerprint.

Cite this