Multistage Sequencing by Hybridization

The sequencing of DNA is an important and difficult problem. Many interesting algorithms combine various technologies in an attempt to sequence long regions of DNA. One such algorithm is sequencing by hybridization (SBH). We briefly review SBH and mention the drawbacks that prevent it from being used in practice. We then present a theoretical algorithm that uniquely determines a sequence of length n through hybridization experiments that require the examination of only O(n2log(n)) subsequences. The key idea is to double subsequence length in each iteration of the algorithm. There are various problems associated with transforming the theoretical algorithm into a practical biological procedure. However, the general strategy of increasing subsequence length may be used to develop algorithms that are feasible given the current state of technology. Combining this strategy with a computer processing phase leads to a novel method of extending the resolving power of standard SBH techniques.