Lecture 10.2: Great Optimization Ideas for Protein Structure Prediction

Recording. Download the text transcript.

Automatic transcript; technical terms and equations may contain recognition errors.

00:00:00 Okay, so I'm about to finish this module of classical protein structure prediction and its various scenarios formulated as optimization. Okay? But in the end, I still want to emphasize the algorithm innovation. I want to ask you, right, even in this case, midnight zone, can we do better than something?

00:00:30 So far, you know, the strategies seem to be, oh yeah, we can do this kind of global or local samples. And MCMC is one way, you know, you can use molecular dynamics and so on. Or you do some more sophisticated non-convex optimization, right? But what can you do to make it better? In this case, we know what better means, right? More efficiency, more likely to reach the global optimum or its neighbors, right?

00:00:58 So I'm going to spend about five to ten minutes to talk about the great ideas. I think they're, I don't want you and I don't need you to learn about the details about these ideas.

00:01:12 But I want you to see where these innovation ideas are coming from. And you can see that if you were put in that moment of history, you can do the same. Right? Because innovation is difficult, but there are very limited ways to innovate.

00:01:29 Right? There's, there's, there's a science to do, to innovate. Okay? So let's see a few examples. Okay?

00:01:36 So let's wrap up this part and, you know, the gradient-free non-local search and just talk about some great optimization ideas. Okay?

00:01:52 So without giving you too much hint, too many hint, from what perspective can I think about novel ideas to improve optimization algorithms for protein structure prediction?

00:02:08 What perspectives can I think of?

00:02:10 What are the elements of optimization?

00:02:28 The elements of optimization?

00:02:30 Objective function.

00:02:31 Objective function.

00:02:32 Constraints.

00:02:34 Constraints.

00:02:35 Decision variable included.

00:02:38 Objective function.

00:02:39 Right?

00:02:40 Right?

00:02:41 Okay.

00:02:42 And beyond optimization algorithm, which follows a principle, I can also ask at the end, is there additional data I haven't used yet?

00:02:55 Isn't it?

00:02:56 We have seen a flavor of that in the Twilight Zone, right?

00:03:00 When we realized that we never used all the template structures.

00:03:04 We only used the template sequences and figure out, oh, this is a good template, so we use that structure.

00:03:10 But we don't look at the other structures, right?

00:03:13 So we'll also consider the possibility of additional data.

00:03:16 Okay?

00:03:17 All right.

00:03:18 So let me try to summarize, because the details are not important, because I want you to think about the algorithmic innovation.

00:03:27 I just want you to learn how to innovate here.

00:03:31 Okay?

00:03:32 I didn't really provide the links here, but I can briefly talk about here.

00:03:38 So first of all, the search space.

00:03:42 All right?

00:03:43 So far you said that atoms are what I need to pay attention to, and I have to consider all these atoms, and I have to consider somehow they are bounded and non-bounded interactions.

00:03:56 Right?

00:03:57 Well, have you thought about the fact that you can coarse-grain the molecular representation from a high dimension to a lower dimensional space?

00:04:07 In the meantime, you can ask, what are the samples in nature?

00:04:13 Can I use the nature-sampled structure fragments to simulate my search space?

00:04:21 Right?

00:04:22 In other words, can I have like Lego pieces?

00:04:26 Right?

00:04:27 Each piece is like three residues that nature has sampled.

00:04:31 It's taking a shape.

00:04:32 Let's use it as Lego pieces.

00:04:34 Okay?

00:04:35 Then when I do the structure prediction, I can consider the nature-sampled fragment structures.

00:04:41 Okay?

00:04:42 Secondly, objective function.

00:04:44 We can consider beyond the energy potentials.

00:04:48 We can learn from data.

00:04:49 We can have the statistical potentials.

00:04:51 Right?

00:04:52 And the search strategies can be improved as well.

00:04:56 And lastly, the constraints or restraints can be also improved.

00:05:01 So I'm going to say something really briefly here.

00:05:03 For instance, the degrees of freedom.

00:05:08 Right?

00:05:09 We can start with a low resolution representation if the high dimensional representation is a problem.

00:05:15 Right?

00:05:16 For instance, you don't consider all hydrogens.

00:05:20 You only consider the backbone non-hydrogen atoms.

00:05:23 And the side chains are not regarded like all the atoms but regarded as a centroid.

00:05:29 Right?

00:05:30 Then you only consider backbone portion of the user freedoms while side chains are centroid.

00:05:35 So that's one way to start.

00:05:37 Right?

00:05:38 In this way, you start with a low resolution representation and easy to optimize objective function.

00:05:44 And then you gradually funnel the candidates into the next stage where you can use a higher resolution representation of the molecule and higher representation of, sorry, higher resolution of the energy functions.

00:05:58 Right?

00:05:59 So that's one thing you can start with.

00:06:00 You can funnel the complexity.

00:06:02 Right?

00:06:03 And then you can reuse or discretize your state space.

00:06:08 Right?

00:06:09 In this case, you can consider, for instance, all the five residue fragments that nature has sampled.

00:06:16 Right?

00:06:17 And then each of them is like a Lego piece.

00:06:19 If you need to predict the structure of ASTU, ASTVO, there's no O, ASTVP, for instance.

00:06:35 Right?

00:06:36 You look at AST.

00:06:37 Right?

00:06:38 For instance, you start with the trimer.

00:06:41 You look at AST, whether there are different AST structures in nature.

00:06:47 Right?

00:06:48 Right?

00:06:49 In nature, we'll have a lot of structures and some of them contain the fragment of AST.

00:06:53 And I say, well, what can AST look like?

00:06:56 Then I have maybe, you know, 3,000 choices in the current library.

00:07:00 And then I just try to assemble one of them with the next and so on.

00:07:04 Right?

00:07:05 So this is another way of discretizing the search space based on the domain knowledge.

00:07:15 Okay?

00:07:16 Because nature has already sampled.

00:07:18 It's not like AST can take all the degrees of freedom as possible.

00:07:22 Okay, that's the search space.

00:07:25 And what about the objective function?

00:07:29 Right?

00:07:30 So, as we said that, well, the principle is great, you know, the energy minimum principle,

00:07:35 but we already have taken so much approximations already from quantum mechanics to molecular mechanics.

00:07:43 There are so many errors in these functions or force fields we are using.

00:07:47 Don't forget that these force fields were also early versions of machine learning because you fit those simple functions.

00:07:55 They are not neural networks.

00:07:56 They are simple functions like QI times QJ divided by RIJ.

00:08:00 Right?

00:08:01 You fit those simple functions to experimentally observed values.

00:08:06 Right?

00:08:07 Data, which is not big data.

00:08:09 Right?

00:08:10 So back then it was done in that way.

00:08:12 So can we complement such knowledge through data or knowledge based statistical potential?

00:08:20 Right?

00:08:21 So that's something we can do.

00:08:23 For instance, right?

00:08:25 You know, maybe the way you describe these functions are now different, but these, uh,

00:08:32 decomposition I think still makes sense because what you need to figure out, the function you want to optimize, is log of the P, or in other words, you are, you know, maximize the probability of the structure given the sequence.

00:08:48 Right?

00:08:49 So that's a function you want to learn.

00:08:51 Right?

00:08:52 Right?

00:08:53 So if you use the Bayes theorem, you can rewrite it as probability of the sequence given the structure, time probability of the structure divided by probability of the sequence.

00:09:01 All right?

00:09:02 So using these guidelines, if you take a log of the P, then you can rewrite this log of the P as a sum of three possibilities.

00:09:14 And each possibility actually can be learned in different ways.

00:09:18 For instance, probability of the sequence given the structure.

00:09:23 Right?

00:09:24 So this is like what we have seen in the threading.

00:09:27 We are asking how comfortable is the query sequence when it's threaded to the template structure.

00:09:34 Right?

00:09:35 So we have a lot of ways to describe this environment, fitness, and so on.

00:09:41 Right?

00:09:42 So we can learn, we can decompose these further into different terms and learn them.

00:09:47 Then there are certain things that are independent of the sequence that are only dependent on the structure.

00:09:52 Then we can use these terms to approximate these functions.

00:09:57 Okay?

00:09:58 And this is one thing about objective function.

00:10:03 And you can keep decomposing.

00:10:07 You can approximate, for instance, the sequence given the structure, for instance.

00:10:12 Right?

00:10:13 Is amino acid 1 through amino acid N given the structure X.

00:10:17 Then you can do the chain rule factorization.

00:10:21 Right?

00:10:22 Then you figure out that, well, if I, you know, ignore the higher order effects, then I ended up just learning these terms.

00:10:32 Right?

00:10:33 The first term is the amino acid at position I given the structure.

00:10:39 So that's the environment probability.

00:10:42 And then you have the joint probability.

00:10:44 I mean, the acid I and J given the structure divided by this product of the two.

00:10:50 If you think they are, you know, marginal.

00:10:53 Right?

00:10:54 Independent marginal.

00:10:55 Right?

00:10:56 So this is like the odds, isn't it?

00:10:58 The probability of the joint divided by the product of the marginal.

00:11:02 Which is the odd.

00:11:03 Right?

00:11:04 You can use this to guide your design of data-driven models.

00:11:10 Right?

00:11:11 So, and the, in the old days, for instance, when they are trying to learn these probability of the structure given the sequence.

00:11:21 You know, there's very limited data.

00:11:25 So they actually had to use a shallow model.

00:11:29 That was a logistical regression.

00:11:31 Right?

00:11:32 And then they had to generate data by themselves.

00:11:34 For instance, they generate a lot of decoys.

00:11:37 Right?

00:11:38 Starting from the native structure.

00:11:39 They perturb the structures by choosing a random residue and replace its phi-sci angles with random values from the protein database.

00:11:49 And then do that iteratively.

00:11:50 So they had to do a lot of such sampling by them.

00:11:55 Sorry.

00:11:56 Data set preparation by themselves.

00:11:58 Okay?

00:11:59 If you carry these questions into, again, I don't need you to pay attention to the details here.

00:12:05 But I want you to carry the philosophy here into understanding the latest alpha-fold later.

00:12:13 When we go to alpha-fold, you may ask yourself, can I follow the similar principle and design a neural network model to learn what probability?

00:12:24 And then what data can I use to learn that probability which is represented as a neural network now?

00:12:33 Right?

00:12:34 So these are the questions I want you to think about.

00:12:36 Because, as I said, just like the classical optimization, just like these early days of data-driven models, the exact forms may be not the state of art, but the innovation ideas and the wisdom are just rejuvenated and reincarconated in the current models.

00:12:59 Okay?

00:13:00 So that's why we really like to learn this classical methods, to learn where innovations came from.

00:13:08 Now, let's talk about the last part.

00:13:14 Okay?

00:13:15 It's about more data.

00:13:16 So sometimes it's not that easy to figure out what more data you can use because you don't know the domain knowledge.

00:13:23 Okay?

00:13:24 So far, we have used the what data so far, including learning the statistical potentials.

00:13:30 What data have we used so far?

00:13:39 What data have we used so far in all these midnight zone, twilight zone, safe zone?

00:13:46 What data have we used?

00:13:53 Let's try.

00:13:54 Anyone want to start?

00:13:55 What data have we used?

00:13:58 The query sequence and what other sequence?

00:14:02 Template sequence.

00:14:03 What template sequence?

00:14:05 What sequences are in the template library?

00:14:12 Yes, but all protein sequences have been utilized or just some of them?

00:14:26 Which ones have we utilized so far?

00:14:33 The ones with structures, right?

00:14:36 Right?

00:14:37 From the safe zone to the twilight zone to this midnight zone when you are learning those probability

00:14:45 in the distributions, right?

00:14:47 You are using sequences with structures, right?

00:14:51 Have we ever used protein sequences without structures?

00:14:55 Have we?

00:14:58 We know that the number of structures is probably three or four orders of magnitude lower than the number of sequences, right?

00:15:07 But we know that that number alone is not a good way to look at it because the structure space is more conserved than the sequence space, right?

00:15:16 But still, there are so many sequence data we haven't utilized yet, right?

00:15:22 That don't have structures.

00:15:24 How do we utilize them?

00:15:26 So that's why I'm saying that it's not that easy.

00:15:30 Sometimes you need to figure out the domain knowledge to utilize it.

00:15:33 So the concept here is coming from evolution, actually.

00:15:38 Evolution.

00:15:39 So let's regard each row as a sequence, okay?

00:15:47 Different rows could correspond to the same family, like in the homologs in different species.

00:15:54 Imagine that this is the hemoglobin protein in rabbits, in moths, in humans, and everything, okay?

00:16:01 And these multiple sequences are already aligned position-wise or residue-wise, okay?

00:16:08 Once they are aligned, you may think about here, for instance, there are two positions, i and j.

00:16:14 Okay?

00:16:16 Then you may wonder why in one species, i equal to alanine, j equal to, you know, phenylalanine,

00:16:24 and in another species, i equal to, for instance, a positively charged residue and j equals to a negatively charged residue.

00:16:32 In other words, the two residues are co-varying over evolution, right?

00:16:40 Then you may wonder what drives them.

00:16:44 One idea is that, look, this protein needs to fold, one-dimensional sequence needs to fold into a three-dimensional structure.

00:16:52 So, if i and j co-evolve, like, when i is big, j is small, when i is changed to small, and j is big,

00:17:01 and then when i is positively charged, then j is negatively charged, and when i is negatively charged, j is changed to be positively charged, and so on.

00:17:10 In other words, if there is some kind of cooperation between i and j in evolution, then most likely in three-dimensional space, i and j are interacting.

00:17:23 That's one explanation, okay?

00:17:25 I'm actually reversing cause and consequence.

00:17:28 So that's not 100% safe.

00:17:30 Because the cause is, if two residues are close in 3D, then they could co-evolve in one-D sequence, okay?

00:17:40 But i'm changing the order now.

00:17:42 I'm saying that, you know, if we observe the sequence co-evolution, then most, then it's possible that the two residues are interacting with each other or close in 3D, okay?

00:17:53 So it's a good assumption, but it's not always safe.

00:17:57 But nevertheless, that was directly contributing to, you know, the first revolution after the classical protein structure prediction, right?

00:18:08 Actually, the first alpha-fold one was directly based on this data, right?

00:18:14 If you look at the features that are most important to alpha-fold one, it's coming from this co-evolution analysis.

00:18:22 Okay?

00:18:23 So it's still, as of today, alpha-fold two is still using multiple sequence alignment, but it's doing things end-to-end now.

00:18:34 It's no longer feeding MSA and learn the co-evolution and use the co-evolution as the features to the model.

00:18:43 It directly feeds MSA directly, okay?

00:18:46 Into the model.

00:18:48 So in other words, the input end is directly reaching the end data, that is MSA.

00:18:53 It's no longer the co-evolution, learn from MSA, multiple sequence alignment anymore, okay?

00:18:59 This is just one kind of data, and there are way more other data that we can consider, okay?

00:19:05 We'll talk about more about this data.

00:19:08 Remember, at the beginning, we talked about what bioinformatics data are out there available, and we can open this discussion again when we talk about the protein structure prediction, okay?

00:19:19 But here, I want you to think about it.

00:19:21 Where are innovations coming from?

00:19:23 Very simple.

00:19:24 You have seen already, right?

00:19:25 In the case of gradient-based algorithms, we follow the principles.

00:19:28 We look at the theoretical expectations.

00:19:31 And in this case, we look at what are the elements of the formulation of optimization if we want to make the principle-driven method much better.

00:19:40 And then in the case of data-driven methods, right, they are not exclusive.

00:19:45 How can I utilize my current data smartly, and how can I utilize additional data?

00:19:51 So there's really very limited ways to innovate, okay?

00:19:57 So let me stop here and summarize that, you know, these great ideas.

00:20:02 Again, no need to look into the details, but I think they're very interesting, that.

00:20:06 First, looking at the elements of optimization, we see how a search-based objective function and the search strategies are being improved.

00:20:15 And then we can look at the co-evolved residues from the additional data, which basically says that, oh, if I and J are co-evolving in sequence, then they must be

00:20:26 contacting in 3D or structure, right?

00:20:30 So there's a lot of integration of knowledge and data.

00:20:34 So the best model you can come up with is the model that integrates knowledge and data perfectly for the questions at hand.

00:20:43 Okay?

00:20:44 We'll see more examples like that.

00:20:46 Okay, let me stop here and then in the, any questions so far?

00:20:53 So this will be the end of the optimization module, okay?

00:20:58 Any questions so far?

00:21:00 [Uncertain recognition] okay?

00:21:02 [Uncertain recognition] okay...

00:21:03 [Uncertain recognition] okay...