Algorithms in Structural Bioinformatics

Computational methods for analyzing, predicting, and designing biomolecules. Covers protein structure and function, folding and structure prediction, optimization, machine learning, protein language models, AlphaFold, and drug design. Students learn to work with sequence and structural data and formulate biological questions as computational problems. Assumes algorithms and programming; no prior biology is required.

Schedule

Weeks follow the recorded lectures, “From Bioinformatics to AI” (Spring 2022, about two a week); topics, readings, and papers are from the Spring 2024 syllabus. The recordings end with attention (lecture 21), so weeks 11–14 are readings and papers.

WeekTopicReading
1Bioinformatics, AI, and biomolecules
  1. 1 Introduction: bioinformatics and AI transcript
  2. 2 Biomolecules (DNA, RNA, protein) and information transcript
Gu & Bourne 1, 3
2Protein structure and its data
  1. 3 Protein structure concepts transcript
  2. 4 Protein structure data transcript
Gu & Bourne 2, 9
3Structure prediction: the classical formulation
  1. 5 Classical formulation of protein structure prediction; optimization transcript
  2. 6 Protein sequence alignment and dynamic programming transcript
Gu & Bourne 30
4Structure prediction: threading and energy minimization
  1. 7 Classical protein structure prediction II transcript
  2. 8 Structure prediction in the midnight zone: energy minimization transcript
Gu & Bourne 31, 8
5Numerical optimization for structure prediction
  1. 9 Gradient-based numerical optimization transcript
  2. 10.1 Gradient-free numerical optimization transcript
  3. 10.2 Great optimization ideas for protein structure prediction transcript
Gu & Bourne 32
5Protein docking
dimensionality reduction and optimization algorithms revisited
Donald 20, 21, 22, 23
Gu & Bourne 24, 25, 26, 27
6Protein function prediction; machine learning
  1. 11.1 Protein function prediction transcript
  2. 11.2 Introduction to machine learning transcript
  3. 12 Shallow machine learning: support vector machines transcript
Gu & Bourne 21, 22
7Machine learning in practice
  1. 13.1 Evaluating classifiers transcript
  2. 13.2 Integrating heterogeneous data transcript
  3. 14 Regression, bias–variance tradeoff, and regularization transcript
  4. 15 Machine learning in practice: diagnostics and fixes transcript
8AI and neural networks
  1. 16.1 Introduction to artificial intelligence transcript
  2. 16.2 AI in healthcare and drug discovery transcript
  3. 17 A first take on neural networks transcript
9Convolutional networks: contact maps as images
  1. 18.1 CNNs: why? transcript
  2. 18.2 CNNs: how? transcript
  3. 18.3 CNNs: what? + case study transcript
  4. 19.1 Neural network computation: model class, loss, and regularization transcript
  5. 19.2 Neural network computation: optimization transcript
Senior et al. 2020 AlphaFold
Senior et al. 2019 AlphaFold at CASP13
10Recurrent networks and attention: sequences as text
  1. 20.0 CNN recap transcript
  2. 20.1 Recurrent neural networks transcript
  3. 20.2 The exploding or vanishing gradient problem transcript
  4. 20.3 Modern RNNs: LSTM and GRU transcript
  5. 20.4 RNNs for protein structure prediction transcript
  6. 21.1 Introducing attention: image captioning transcript
  7. 21.2 Introducing attention: language translation transcript
11Protein language models
transformers; representation learning; self-supervised pre-training and fine-tuning; transfer learning; predicting structure, interactions, and mutational effects from embeddings
123D structure from sequence: AlphaFold 2 and ESMFold
multimodal learning over text, graphs, and point clouds; graph neural networks; roto-translationally equivariant networks; protein function and interactions as graphs
13Drug discovery: from computer-aided to AI-driven design
the drug discovery and development process; energy-based combinatorial optimization; inverse design from property to molecule; generative models: GANs, VAEs, flows, diffusion
Gu & Bourne 34
14Black box no more?
physical constraints and domain knowledge in deep learning; interpretability and explainability
14Biomolecular systems modeling
topology, steady states, and dynamics; new AI approaches
15Final project presentations

Final project

Pick a problem where an application and an algorithm meet. Either benchmark established methods (at least one new to the application) and explain why they work or fail, or propose a change to a method, motivated by a hypothesis about the application, and test whether it helps. Teams of up to three. Dates are from Spring 2024.

Feb 19Read the guidelines and project ideas; form a team.
Feb 21–28Meet the instructor to pitch and refine the idea.
Mar 10Proposal, 2 pages: problem, significance, current methods and their gaps; proposed method, rationale, data, assessment, timeline.
Apr 4Progress update, 2 pages: progress, obstacles, current results, expected outcomes, updated timeline.
Apr 23–30Presentation, 15 minutes including questions: problem, method and rationale, results and insights.
May 3Final report, 6–8 pages in paper format.

References

Texts

Papers

  • [Rives2021]A Rives et al. Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences. PNAS 118(15), 2021. PDF
  • [Bepler2021]T Bepler and B Berger. Learning the protein language: Evolution, structure, and function. Cell Systems 12(6), 2021. PDF
  • [Marquet2022]C Marquet et al. Embeddings from protein language models predict conservation and variant effects. Human Genetics 141, 2022. PDF
  • [Senior2020]AW Senior et al. Improved protein structure prediction using potentials from deep learning. Nature 577, 2020. PDF
  • [Senior2019]AW Senior et al. Protein structure prediction using multiple deep neural networks in the 13th Critical Assessment of Protein Structure Prediction (CASP13). Proteins 87(12), 2019. PDF
  • [Jumper2021]J Jumper et al. Highly accurate protein structure prediction with AlphaFold. Nature 596, 2021. PDF
  • [Lin2023]Z Lin et al. Evolutionary-scale prediction of atomic-level protein structure with a language model. Science 379(6637), 2023. PDF
  • [Nijkamp2023]E Nijkamp et al. ProGen2: Exploring the boundaries of protein language models. Cell Systems 14(11), 2023. PDF
  • [Ingraham2023]JB Ingraham et al. Illuminating protein space with a programmable generative model. Nature 623, 2023. PDF