This project explores a new approach to sequencing by hybridization (SBH), which uses interaction to dramatically reduce the number of oligonucleotides for de novo sequencing of large DNA fragments, while preserving the parallelism which is the primary advantage of SBH. The goals of the project include: (1) Development of efficient algorithms for the interactive design of sequencing chips; and (2) Utilization of simulation results to establish that 64kb fragments can be sequenced (obtained using approximately ten rounds of standard-sized 64k oligonucleotide arrays). The project includes the following theoretical and laboratory research in interactive SBH: (a) In a collaborative effort with biochemists at Oxford University, England, algorithmic issues in the design and manufacture SBH arrays, under a variety of fabrication technologies, are examined; (b) Algorithmic issues inherent in reconstructing DNA sequences from hybridization data, under complications such as non-classical chip designs and hybridization errors, are studied; and (c) Algorithmic issues inherent in other novel variations of SBH, particularly photolithography-based interactive SBH and positional SBH, are investigated. This project is jointly funded with the Computational Biological Activity.***
