3-D Structure in Chemistry and Molecular Biology

Contents

The CS-Bio seminar is open to graduate students, and advanced undergraduates with a background in both algorithms and systems (at least CS 25 and CS 23). No background in biology is required, but students should be interested in doing some outside reading in biochemistry. Students will be required to present papers in the seminar. Non-CS students (e.g., in biology and chemistry) with an interest in computational issues are invited as well; please speak with me about your background first though.

• 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.
  • CPM 1992 = Combinatorial Pattern Matching, Third Annual Symposium.

• 3/31
  No Class. Prof. Donald at NSF.
• 4/2
  First Class. Introduction to Computational Biology and Chemistry.
  Reading: Principles of Protein Structure
  Reading: Biology Hypertextbook

  Do these tasks:

  • Read about and download RasMol on your machine to be able to view and manipulate biopolymers.
  • To read the papers, you will need to be able to download and print PostScript files and Adobe PDF files from the WWW. Please familiarize yourself with how to do this.
• 4/7
  Abstract
  Reading: De Novo Protein Design: Fully Automated Sequence Selection [PDF]
  Science (1997) October 3; 278 (5335):82 B. I. Dahiyat and S. L. Mayo.
  • Help with PDF files.
  Presenting: Bruce Donald.
  
  • Introductory Reading:
    • Protein Geometry and Modelling [Gzipped PostScript]
  • Background Reading:
    • Clinical significance of Protein Science [PDF]
    • Transcription factors (DNA-binding Proteins) for control of gene expression
      • A more detailed paper on transcription factors [PDF]
• 4/9
  Computational Problems in NMR Structural Biology
  Presenting: Dan Gessel.
  Reading:
  • How to give a good talk
  • Review of NMR:
    • "Structure Determination: Nuclear Magnetic resonance Spectroscopy", Chapter 13 in "Organic Chemistry" by J. McMurry (Brooks/Cole) pp 442-486.
    • Tutorials, Notes, and References on NMR
  • Primary Reading:
    • P. Guntert, C. Mumenthaler, K. Wuthrich. "Torsion Angle Dynamics for NMR Structure Calculation with the New Program Dyana", J. Mol. Bio (1997) 273. pp 283-298.
    • C. Mumenthaler, P. Guntert, W. Braun, K. Wuthrich. "Automated combined assignment of NOESY spectra and three-dimensional protein structure determination," J. Biomolecular NMR, 10 (1997) 351-362.
• 4/13
  Geometry and the Discovery of New Ligands
  Presenting: Ryan Lilien
  Reading:
  • Background:
    • Methods for Structure Based Drug Design , Hugo O. Villar and Ryan T. Koehler, The Molecular Modeling Electronic Conference, Issue 3, Oct.-Dec. (2), 1998.
  • Introduction:
    • Lydia E. Kavraki. "Geometry and the Discovery of New Ligands." International Workshop on the Algorithmic Foundations of Robotics (WAFR), Toulouse France (1996).
  • Primary Reading:
    • Andrew Leach, "A survey of methods for searching the conformation space of small and medium-sized molecules."
    • Read Chapter 10 in textbook by Leach, pp. 543-568.
• 4/16
  Computational Problems in X-ray Crystallography
  Presenting: Bruce Donald.
  • Reading:
    • J. Drenth, "Principles of Protein X-ray Crystallography", chapters 4 and 7.
    • Joseph Roenblatt and Paul D. Seymour, "The Structure of Homometric Sets." SIAM J. Alg. Disc. Meth., Vol. 3, No. 3, September 1982.
• 4/21 - 4/23
  No Class. Prof. Donald at Purdue.
• 4/28
  Protein Folding 1
  Presenting: Keith Kotay
  • 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.
  • K. Dill and H. S. Chan. "From Levinthal to pathways to funnels", Nature Structural Biology, (4) 1 (January, 1997).
  Presenting: Michael L. Chalfant
  • 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.
• 4/30
  Protein Folding 2
  Presenting: Scot Drysdale
  • 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.
  • J. T. Ngo, J. Marks, Computational complexity of a problem in molecular-structure prediction, Protein Engineering, vol 5, no 4, pp. 313-321, 1992.
    • Thus just in: Protein Folding in the 2D discrete lattice HP model is proven NP-complete. Here is the paper [PostScript].
• 5/5
  Structural Domains in Proteins
  Presenting: Zie Kone
  • G.M. Crippen, ``The tree structural organization of proteins.'' JMB 126(1979), 315.
  • L. Holm, C. Sander. ``Parser for protein folding units.'' PSFG 19(1994), 256.
  • L. Holm, C. Sander. ``Searching protein structure databases has come of age.'' PSFG 19(1994), 165.
  Presenting: Joe Edelman
  • G.D. Rose. ``Hierarchic organization of domains in globular proteins.'' JMB 134(1979), 447.
  • R. Srinivasan, G.D. Rose. ``LINUS: A hierarchic procedure to predict the fold of a protein.'' PSFG 22(1995), 81.
• 5/6 (X-hour, 4PM)
  Structural Domains in Proteins (Continued)
  Presenting: Zie Kone
  • L. Holm, C. Sander. ``Parser for protein folding units.'' PSFG 19(1994), 256. (Focus on the Eigenproblem).
  • Band diagonal matrices and graph bandwidth.
• 5/7
  Distance Geometry and Molecular Conformation 1
  Presenting: Jay Aslam
  • G.M. Crippen, T.F. Havel, "Distance Geometry and Molecular Conformation." Research Studies Press LTD, 1988, pp.1--23, 139--191.
  • Here is a wonderful textbook that covers the Singular Value Decomposition (SVD), Penrose pseudo-inverse, and other useful numerical methods.
  • polynomial time approximation schemes.
• 5/12
  Distance Geometry and Molecular Conformation 2
  Presenting: Robert Savell
  • 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.
  Presenting: Tilmann Steinberg
  • B. Berger, J. Kleinberg, F.T. Leighton. Reconstructing a Three-Dimensional Model with Arbitrary Errors. Proc. 28th ACM Symposium on Theory of Computing, 1996. Postscript.
• 5/14
  Direct Methods for the Phase Problem of x-Ray Crystallography
  Presenting: Senthil Periaswamy
  • 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.
  Presenting: Michael Chalfant
  • 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.
• 5/19
  Overview Articles on Molecular Similarity and Protein Resemblance
  Presenting: Emily Cornell
  • L. Holm, C. Sander. ``Mapping the protein universe.'' Science 273(1996), 595.
  • Approximating the bandwidth via volume respecting embeddings
  • 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 1
  Presenting: Zie Kone
  • G. Milne, S. Wang, M. Nicklaus. ``Molecular modeling in the discovery of drug leads.'' JCICS 36(1996), 726.
  • RAPID: Randomized Pharmacophore Identification for Drug Design. P.W. Finn, L.E. Kavraki, J.C. Latombe, R. Motwani, C. Shelton, S. Venkatasubramanian, and A. Yao. Proc. of 13th ACM Symp. on Computational Geometry (SoCG'97), pp. 324-333, 1997. A revised version of this paper will also to appear in Computational Geometry: Theory and Applications.
• 5/21
  Geometric Similarity in Drug Design 2
  Presenting: Tilmann Steinberg
  • 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.
  Geometric Hashing 1
  Presenting: Ryan Lilien
  • Daniel Fischer, Ruth Nussinov, Haim J. Wolfson: 3-D Substructure Matching in Protein Molecules. CPM 1992: 136-150
  • Daniel Fischer, Raquel Norel, Ruth Nussinov, Haim J. Wolfson: 3-D Docking of Protein Molecules. CPM 1993: 20-34
• 5/26
  Geometric Hashing 2
  Presenting:Cliff Stein
  • 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.
  Presenting: Keith Kotay
  • 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).
• 5/28
  Geometric Similarity for Protein Structure Comparison
  Presenting: Neil Miller
  
  • 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).
  Presenting: Robert Savell
  • 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.
• 6/2
  Speculation, Discussion, Open Problems
  Last day of class.
  We will discuss what complexity results could mean, both computationally and biophysically. We'll also discuss open problems and the future of computational biology.
  • J. Thomas Ngo, Joe Marks and Martin Karplus, "Computational Complexity, Protein Structure Prediction, and the Levinthal Paradox," in The Protein Folding Problem and Tertiary Structure Prediction, Kenneth Merz, Jr. and Scott LeGrand, eds., pp. 433-506, Birkhauser, Boston, 1994 [PostScript, 202K].

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

Some Relevant WWW Links