MULTISTAGE SEQUENCING BY HYBRIDIZATION

The sequencing of DNA is an important and difficult problem. Many inte resting algorithms combine various technologies in an attempt to seque nce long regions of DNA, One such algorithm is sequencing by hybridiza tion (SBH). We briefly review SBH and mention the drawbacks that preve nt it from being used in practice. We then present a theoretical algor ithm that uniquely determines a sequence of length n through hybridiza tion experiments that require the examination of only O(n(2)log(n)) su bsequences. The key idea is to double subsequence length in each itera tion of the algorithm. There are various problems associated with tran sforming the theoretical algorithm into a practical biological procedu re, However, the general strategy of increasing subsequence length may be used to develop algorithms that are feasible given the current sta te of technology. Combining this strategy with a computer processing p hase leads to a novel method of extending the resolving power of stand ard SBH techniques.