Sequencing by Hybridization with Noisy Inputs

Sequencing by hybridization (SBH) is a proposed method for obtaining the base-by-base sequence of an unknown nucleic acid molecule in two steps: hybridization of fragments of the unknown DNA molecule to known subsequences, and reconstruction of the entire unknown sequence from the hybridization spectrum. Work in computer science has produced algorithms for the reconstruction process approaching information-theoretic bounds, but most treatments have ignored the effect of physical hybridization noise. I have been working on this problem by modeling the effect of noisy inputs on SBH algorithms and by calculating bounds on their reconstruction fidelity. This talk will give the progress of this effort.