3-D Structure in Chemistry and Molecular Biology!

Computer Science 787
Fall 1997

Tuesday 3:00 - 4:30 PM
Upson Hall Room 5130

Contents

Organizers Overview Schedule List of Papers Some Relevant WWW Links


Organizers

Klara Kedem
kedem@cs.cornell.edu , 5149 Upson, 255-9208.
Paul Chew
chew@cs.cornell.edu , 721 Rhodes, 255-9217.
Jon Kleinberg
kleinber@cs.cornell.edu , 5134 Upson, 255-3600.
Dan Huttenlocher
dph@cs.cornell.edu , 4119 Upson, 255-3036.


Overview

Our goal is to look at some algorithmic problems related to three-dimensional structures in chemistry and molecular biology, primarily from the perspective of computational geometry. We hope to consider a variety of topics (guided by the interests of the participants), and to make the seminar interesting to people with as wide a range of backgrounds as possible.


Schedule

The schedule for the first few weeks of the semester is as follows.

  • Week 1 (9/2): Jon Kleinberg will talk about discrete lattice models for protein folding (and relate this to the protein folding problem in general). This will also cover some algorithmic work on lattice models in the theoretical computer science community. See references below for papers.
  • Week 2 (9/9): Klara Kedem will talk about geometric approaches to identifying structural domains in proteins, including a description of the LINUS algorithm of Srinivasan and Rose. See references below for papers.
  • Week 3 (9/16): Bob Connelly will talk about methods from distance geometry and rigidity theory for analyzing three-dimensional structures from distance data.
  • Week 4 (9/23): Steve Vavasis will talk about direct methods for the phase problem of x-ray crystallography.
  • Week 5 (9/30): No meeting.
  • Week 6 (10/7): Pedro Felzenszwalb will present surveys on 3D molecular similarity and protein resemblance.
  • Week 7 (10/14): No meeting (fall break).
  • Week 8 (10/21): Jim Ezick will talk about geometric similarity in drug design.
  • Week 9 (10/28): Paul Chew will talk about our preliminary results in problems evolving from the CS-Bio seminar.
  • Week 10 (11/4): Cathy Stenson will talk on analysis of conformational coverage..
  • Week 11 (11/11): Joanne Button will talk on hydrogen bonds.
  • Week 12(11/18): Debra Goldberg will talk about geometric similarity for protein structure comparison.
  • Week 13 (11/25): Paul Chew will continue with his discussion about preliminary results in problems evolving from the CS-Bio seminar.
  • Week 14 (12/2): Dan Brown will talk on geometric hashing.


    • List of Papers

    Below, we list some papers on topics that might be covered in the seminar. The exact list will be refined as time goes on ...

    We use some abbreviations for various journals and conference proceedings below:

  • SCG = Proceedings of the ACM Symposium on Computational Geometry
  • JMB = Journal of Molecular Biology
  • PSFG = Proteins: Structure, Function, and Genetics
  • JCICS = J. Chem. Inf. Comput. Sci.

    • Discrete Lattice Models (Week 1)

  • K. Dill, S. Bromberg, K. Yue, K. Fiebig, D. Yee, P. Thomas, H.S. Chan. ``Principles of protein folding -- A perspective from simple exact models.'' Protein Science 4(1995), 561.
  • W.E. Hart, S. Istrail. ``Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal.'' Proceedings of the ACM Symposium on Theory of Computing 1995, 157.
  • R. Agarwala, S. Batzoglou, V. Dancik, S. Decatur, M. Farach, S. Hannenhalli, S. Skiena. ``Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model.'' Proceedings of the ACM-SIAM Symposium on Discrete Algorithms 1997, 390.

    • Structural Domains in Proteins (Week 2)

  • G.M. Crippen, ``The tree structural organization of proteins.'' JMB 126(1979), 315.
  • G.D. Rose. ``Hierarchic organization of domains in globular proteins.'' JMB 134(1979), 447.
  • L. Holm, C. Sander. ``Parser for protein folding units.'' PSFG 19(1994), 256.
  • R. Srinivasan, G.D. Rose. ``LINUS: A hierarchic procedure to predict the fold of a protein.'' PSFG 22(1995), 81.
  • L. Holm, C. Sander. ``Searching protein structure databases has come of age.'' PSFG 19(1994), 165.

    • Distance Geometry and Molecular Conformation (Week 3)

  • G.M. Crippen, T.F. Havel, "Distance Geometry and Molecular Conformation." Research Studies Press LTD, 1988, pp.1--23, 139--191.
  • B. Hendrickson, "Conditions For Unique Graph Realizations." Siam Journal of  Computing, Vol. 21, No. 1, February 1992, pp. 65--84.
  • B. Hendrickson, "The Molecule Problem: Exploiting Structure in Global Optimization." Siam Journal of Computing, Vol. 5, No. 4, November 1995, pp. 835--857.

    • Direct Methods for the Phase Problem of x-Ray Crystallography (Week 4)

  • G. Bricogne, "Direct Phase Determination by Entropy Maximization and Likelihood Ranking: Status Report and Perspectives." Acta Cryst. (1993). D49. 37--60.
  • George T. DeTitta et al, "Structure Solution by Minimal-Function Phase Refinement and Fourier Filtering. I. Theoretical Basis." Acta Cryst. (1994). A50, 203--210.
  • Joseph Roenblatt and Paul D. Seymour, "The Structure of Homometric Sets." SIAM J. Alg. Disc. Meth., Vol. 3, No. 3, September 1982.
  • Steven S.Skiena, Warren D.Smith, Paul Lemke, "Reconstructing Sets From Interpoint Distances (Extended Abstract)." 1990 ACM 0-89791-362-0/90/0006/0332.

    • Overview Articles on Molecular Similarity and Protein Resemblance (Week 6)

  • L. Holm, C. Sander. ``Mapping the protein universe.'' Science 273(1996), 595.
  • J-P. Doucet, J. Weber. ``Molecular similarity.'' in Computer-Aided Molecule Design: Theory and Applications.". Springer, 1996. pp. 328--362.

    • Geometric Similarity in Drug Design (Week 8)

  • G. Milne, S. Wang, M. Nicklaus. ``Molecular modeling in the discovery of drug leads.'' JCICS 36(1996), 726.
  • P. Indyk, R. Motwani, S. Venkatasubramanian. "Geometric Matching under Noise: Combinatorial Bounds and Algorithms."
  • P.W. Finn, L.E. Kavraki, J.C. Latombe, R. Motwani, S. Venkatasubramanian. ``Search techniques for rational drug design.''
  • P.W. Finn, L.E. Kavraki, J.C. Latombe, R. Motwani, C. Shelton, S. Venkatasubramanian, A. Yao. ``RAPID: Randomized pharmacophore identification for drug design.'' SCG 1997, 324.
  • T. Akutsu, H. Tamaki, T. Tokuyama. ``Distribution of distances and triangles in a point set and algorithms for computing the largest common point sets." SCG 1997, 314.
  • T. Akutsu, M.M. Halldorsson. ``On the approxiamtion of largest common subtrees and largest common point sets.'' Lecture Notes in Computer Science 834, Springer, 1994, 405.

    • CS-Bio Seminar Topics (Week 9)

  • Background and Partial results on problems evolving from the Bio-CS seminar (post script version, dvi version)

    • Analysis of Conformational Coverage (Week 10)

  • Andrew Smellie, Scott D. Kahn, and Steven L. Teig. "Analysis of Conformational Coverage. 1. Validation and Estimation of Coverage." J. Chem. Inf. Comput. Sci., 1995, 35, 285-294.
  • Andrew Smellie, Scott D. Kahn, and Steven L. Teig. "Analysis of Conformational Coverage. 2, Applications of Conformational Models." J. Chem. Inf. Comput. Sci., 1995, 35, 295-304.
  • Lydia E. Kavraki. "Geometry and the Discovery of New Ligands." Stanford University, Stanford, CA.

    • Hydrogen Bonds (Week 11)

  • J. Bernstein, R.E. Davis, L. Shimoni, N.L. Chang. ``Patterns in hydrogen bonding: Functionality and graph set analysis.'' Angewandte Chemie (International Edition in English) 34(1995), 1555.
  • Hans C. Andersen. "Cluster expansions for hydrogen-bonded fluids. I. Molecular association in dilute gases." Journal of Chemical Physics, Vol. 50, number 9, Nov. 1, 1973.
  • Hans C. Andersen. "Cluster expansions for hydrogen bonded fluids. II. Dense liquids.", Journal of Chemical Physics, Vol. 61, number 12, Dec. 15, 1974.

    • Geometric Similarity for Protein Structure Comparison (Week 12)

  • Liisa Holm and Chris Sander. "An Evolutionary Treasure: Unification of a Broad Set of Amidohydrolases Related to Urease." PROTEINS: Structure, Function, and Genetics 28:72-82, Wiley-Liss, Inc., 1997.
  • Gerrit Vriend and Chris Sander, "Detection of Common Three-Dimensional Substructures in Proteins." PROTEINS: Structure, Function, and Genetics 11:52-58 (1991).
  • Christine A. Orengo, Nigel P. Brown, and William R. Taylor, "Fast Structure Alignment for Protein Databank Searching." PROTEINS: Structure, Function, and Genetics 14:139-167 (1992).
  • Helen M. Grindley, Peter J. Artymiuk, David W. Rice, and Peter Willett, "Identification of Tertiary Structure Resemblance in Proteins Using a Maximal Common Subgraph Isomorphism Algorithm." J. Mol. Biol. (1993) 229, 707-721.
  • Liisa Holm and Chris Sander, "Protein Structure Comparison by Alignment of Distance Matrices." J. Mol. Biol. (1993) 233, 123-138.

    • CS-Bio Seminar Topics (Week 13)

    Geometric Hashing (Week 14)

    Daniel Fischer, Raquel Norel, Ruth Nussinov, Haim J. Wolfson. "3-D Docking of Protein Molecules."

  • Daniel Fischer, Ruth Nussinov, Haim J. Wolfson. "3-D Substructure Matching in Protein Molecules."
  • Haim J. Wolfson. "Model-Based Object Recognition by Geometric Hashing."
  • Yehezkel Lamdan, Haim J. Wolfson. "Geometric Hashing: A General and Efficient Model-Based Recognition Scheme." Proceedings of the Second International Conference on Computer Vision, Tampa, FL, December 5-8, 1988.
  • Bilha Sandak, Ruth Nussinov and Haim J. Wolfson. "Docking of Conformationally Flexible Proteins." Lecture Notes in Computer Science, Combinatorial Pattern Matching, 7th Annual Symposium, CPM 96, Laguna Beach, CA, June 1996.
  • Daniel Fischer, Shuo Liang Lin, Haim J. Wolfson and Ruth Nussinov. "A Geometry-based Suite of Molecular Docking Processes." JMB (1995) 248, 459-477.
  • Raquel Norel, Shuo L. Lin, Haim J. Wolfson, and Ruth Nussinov. "Shape Complementarity at Protein-Protein Interfaces." Biopolymers, Vol. 34, 933-940 (1994).

    • Other Papers

    Simplified Geometric Models of Protein Folding

  • S. Sun. P.D. Thomas, K. Dill. ``A simple protein folding algorithm using a binary code and secondary structure constraints.'' Protein Engineering 8(1995), 769.
  • K. Yue, K. Dill. ``Folding proteins with a simple energy function and extensive conformational searching.'' Protein Science 5(1996), 254.

    • Geometric Similarity in Drug Design

  • G. Milne, S. Wang, M. Nicklaus. ``Molecular modeling in the discovery of drug leads.'' JCICS 36(1996), 726.

    • Hydrogen Bonds in Proteins

  • I.K. McDonald, J.M. Thornton. ``Satisfying hydrogen bonding potential in proteins.'' JMB 238(1994), 777.
  • R.W.W. Hooft, C. Sander, G. Vriend. ``Positioning hydrogen atoms by optimizing hydrogen-bond networks in protein structures.'' PSFG 26(1996), 363.

    • Some Relevant WWW Links

  • A large resource page on computational biology at George Mason University.
  • A large resource page on bioinformatics at the Institut Pasteur.
  • CARB Biocomputing Resources.
  • A list of protein folding groups on the web.
  • The WWW Virtual Library page on biomolecules.

    • Return to top of page