Sequencing by Hybridization (SBH) is a challenging alternative to the classical DNA sequencing methods. Several SBH problems must still be jointly addressed by biochemists, computer scientists and instrument designers. In this proposal we address computer science aspects of SBH and hope to bring these communities into closer contact. Some unsolved computer science problems seriously slow down the development of biochemical and instrumentation aspects of SBH. In close collaboration with biology and instrumentation SBH groups we identified the most important computer science problems which need to be addressed to benefit the further development of SBH. The proposal describes a project to study these problems. * User-friendly SBH software in public domain within the first year. * Algorithms and software for sequence reconstruction by optimized chips. * Algorithms and software allowing biologists to check their hypothesis and to optimally choose additional biochemical experiments for SBH. * Algorithms and software to eliminate """"""""blind"""""""" choice of PCR primers by SBH data and reduce the amount of conventional sequencing in molecular evolution studies. * Algorithms and software to combine small-scale SBH and primer walking DNA sequencing and to parallelize ordered sequencing strategies. * Computational analysis of PCR-SBH and estimation of resolving power of PCR-SBH.
| Dancik, V; Hannenhalli, S; Muthurkrishnan, S (1997) Hardness of flip-cut problems from optical mapping. J Comput Biol 4:119-25 |
| Agarwala, R; Batzoglou, S; Dancik, V et al. (1997) Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. J Comput Biol 4:275-96 |
| Belyi, I; Pevzner, P A (1997) Software for DNA sequencing by hybridization. Comput Appl Biosci 13:205-10 |
| Hannenhalli, S; Feldman, W; Lewis, H F et al. (1996) Positional sequencing by hybridization. Comput Appl Biosci 12:19-24 |
| Mironov, A A; Alexandrov, N N; Bogodarova NYu et al. (1995) DNASUN: a package of computer programs for the biotechnology laboratory. Comput Appl Biosci 11:331-5 |
| Hannenhalli, S; Chappey, C; Koonin, E V et al. (1995) Genome sequence comparison and scenarios for gene rearrangements: a test case. Genomics 30:299-311 |
| Rubinov, A R; Gelfand, M S (1995) Reconstruction of a string from substring precedence data. J Comput Biol 2:371-81 |
| Razgulyaev, O; Rubinov, A; Gelfand, M et al. (1995) Sequencing potential of nested strand hybridization. J Comput Biol 2:383-95 |
| Feldman, W; Pevzner, P (1994) Gray code masks for sequencing by hybridization. Genomics 23:233-5 |
| Pevzner, P A (1994) Rearrangements of DNA sequences and SBH. Comput Chem 18:221-3 |
