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.

Agency
National Institute of Health (NIH)
Institute
National Human Genome Research Institute (NHGRI)
Type
Research Project (R01)
Project #
1R01HG000987-01
Application #
2209237
Study Section
Genome Study Section (GNM)
Project Start
1994-02-07
Project End
1997-01-31
Budget Start
1994-02-07
Budget End
1995-01-31
Support Year
1
Fiscal Year
1994
Total Cost
Indirect Cost
Name
Pennsylvania State University
Department
Biostatistics & Other Math Sci
Type
Schools of Arts and Sciences
DUNS #
City
University Park
State
PA
Country
United States
Zip Code
16802
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