Lecture 8: Protein Structure Prediction in Midnight Zone: Energy Minimization.
Recording. Download the text transcript.
Automatic transcript; technical terms and equations may contain recognition errors.
00:00:00 .
00:00:22 Okay, let's get started. Howdy. So welcome back to ECEN 766.
00:00:28 So as we all know, today we are stepping into the midnight zone of protein structure prediction.
00:00:36 So far we have been using protein structure prediction as a very simple, well in quotation,
00:00:43 problem of translating from a 1D modality to 3D modality problem, right?
00:00:50 And you see that how this problem has been formulated before in a case-by-case scenario, right?
00:00:57 We have seen that starting from the early days when the data is relatively limited and people pay attention
00:01:05 to the labeled and paired data. In other words, the pairs of X and Y, input-output, or sequence and structures,
00:01:13 they try to find a pattern and find out how much they can leverage that pattern in their algorithm, right?
00:01:20 And then we have seen that how this problem can be sort of divided and conquered.
00:01:28 So in different scenarios, depending on how much the data can be leveraged, we could solve them in different ways, right?
00:01:36 So as a reminder, in the right here, so in the saved zone, right, so we have seen how this problem can be formulated as database search and sequence alignment,
00:01:53 and more specifically optimization problems. We have, after translating or modeling these problems, we have asked ourselves,
00:02:04 what do we want from algorithms? Do we need algorithms to solve these problems? What concerns are there, right?
00:02:10 We have learned optimization algorithms, what is needed? Accuracy, complexity, and robustness, right?
00:02:19 We also have learned how we can introduce algorithmic innovation as we move from the safe zone to twilight zone,
00:02:31 when the sequence similarity is not significant enough to indicate structure similarity. So in those cases,
00:02:40 we had to resort to weaker signals, not similar sequences, but similar profiles,
00:02:47 profiles, which are generalized sequences. So instead of a fixed sequence, it's like a smeared sequence. Each character is not a single character,
00:02:57 but a distribution over 21 dimensions, 20 amino acids plus one gap, right?
00:03:04 Because of the weaker signals, right, the similar profiles are going to tell you weaker identities as well,
00:03:12 in the sense that it's not similar structure, but a similar structure of folds. And remember, we have hundreds of thousands of structures,
00:03:20 but they, based on how secondary structures are organized, can be categorized into low thousands of folds, right?
00:03:29 But what's striking there was we were asking ourselves, right, it's either principle or data, right?
00:03:37 So what data can be additionally utilized in this twilight zone when we have very weak signals, similar profiles,
00:03:50 to tell something that's not as high resolution as structures, but folds, right? What do we do?
00:03:56 We learned that, indeed, there are additional data we haven't utilized in the safe zone, right?
00:04:04 In the safe zone, we utilized the template sequences, all the template sequences, because we do the sequence alignment,
00:04:12 right? Either heuristics or precisely, right? And for those few identified template sequences,
00:04:22 we're going to use their structures, right? But we never used all other, you know, structures at all, right?
00:04:30 So that gives us a hint that, well, in the twilight zone, we can utilize those data and ask ourselves,
00:04:38 if we now, instead of align the query sequence to the template sequence, what if we align the query sequence
00:04:48 to the template structure or fold and ask, how does it like it, right? How does it like the fold?
00:04:54 And we have learned that if you represent the template structure using one-dimensional descriptors,
00:05:03 then it's essentially the same as aligning two sequences, right? Just these sequences are now written in multiple alphabets, right?
00:05:12 You can still use dynamic programming. But also that comes, that tells you something additional, right?
00:05:19 So if you want to further improve, right? So early methods did use that approach. But if you want to further improve
00:05:27 the accuracy, what else have you not utilized yet? Well, we only utilized the per residue properties,
00:05:36 the 1D descriptors from the template structure. But we never utilized the pairwise and the multi-body
00:05:44 interactions across the residues in the template, right? So that's exactly what RaptorX was utilizing.
00:05:53 Of course, this additional information brings additional opportunity, but also brings challenges,
00:06:03 because now it's no longer, you know, it's no longer a problem that can be easily solved by alignment.
00:06:12 So it's actually MPHard, and we had to formulate it using integer programming. By the way, it is still MPHard, okay?
00:06:22 Formulating it as integer programming does not make the problem easier. It's still MPHard, but we could
00:06:28 heuristically, right, relax the problem into linear programming, let those binary x or y's to be
00:06:36 between 0 and 1 instead of either 0 or 1, right? Then we can solve the linear programming, we know exactly what to do,
00:06:44 then round those non-integer solutions to the binary integers, the nearest ones. So those are things we have learned.
00:06:53 So as said earlier, today we are entering the midnight zone. And before starting, I want to say that
00:06:59 thanks to your responses to the doodle, unfortunately we could not find a time that works for everybody.
00:07:08 But, you know, for those who cannot make it, first I have to clarify that I know Nummy you cannot do it.
00:07:14 I don't mean that you have to be available for the whole 90 minutes. As long as you can find at least
00:07:20 a certain minutes in that 90 minutes, that will be fine, because most likely, you know, you were discussed
00:07:26 about final projects or anything, and there will be multiple people in the slot. Would that work for you?
00:07:33 Okay, if not, we can reschedule and have a different time for your, you know, one-to-one discussion, okay?
00:07:40 Well, utilize office hours and we'll use additional hours as needed for your learning needs. We had the first
00:07:48 round feedback from you in lecture one, those questionnaires, so now I think you have a little bit
00:07:54 more idea about what is taught, and you have probably more detailed ideas about what you need, so we can talk
00:08:02 about that. And then what kind of desire to find a project? So, well, we'll give some guidelines about
00:08:10 the final projects, but it's essentially about the matching between the models, slash data, and
00:08:17 applications. So you may be interested in some kind of model data, like you're interested in sequence or
00:08:23 text data, and you're interested in natural language processing, or you're interested in graph modeling,
00:08:30 and then you may or may not be interested in some kind of applications at the molecular level, systems
00:08:35 level, imaging, and it could be any. So if you are interested in anything in the data, slash model part,
00:08:43 if you are interested in anything in the application part, if you have any idea, any preference,
00:08:50 talk to me, and we can tailor those projects for you. And we'll also make sure that these projects are
00:08:57 doable given the time. So the best idea is start with some paper with their GitHub repo, with data
00:09:05 and models available. Okay, we don't want to start everything from scratch. And we'll also start journal
00:09:12 clubs as we enter the deep learning portion. So I think we had lost one lecture due to the snowstorm.
00:09:23 Otherwise, we would finish the optimization module this week. So if not this, then next Tuesday.
00:09:30 Then we'll talk about machine learning using four lectures. Then after that, we're entering the deep
00:09:37 learning modules. And then that's where we need general club presentations from you. And we'll make
00:09:45 announcements and ask for your preference. Okay? Any questions about this notice as well as last week's
00:09:54 we assigned the homework one. Any questions? Anything? Any questions? Okay. Let me know if you have any
00:10:03 questions. And so we can start this office hours this Thursday. Okay?
00:10:09 So it's going to be in person? Oh, it's going to be Zoom. I will send through the cameras. Okay? It will be Zoom.
00:10:18 Yeah, thanks for asking.
00:10:23 Okay, so now midnight zone, right? Seemingly
00:10:28 I will say homology has reached its limit. Right? We try to expand the definition of homology from sequence to profiles. Right?
00:10:41 Seemingly we are reaching a limit. Okay?
00:10:44 So today we're going to talk about the midnight zone. When the best candidate you could ever find is with sequence identity less than 20%, then
00:10:52 pretty much you have no hope to borrow its structure. Okay?
00:10:55 If in the twilight zone the problem is you don't know which one to borrow. Right? Because they are all 20 to 30%.
00:11:02 In this case most likely you have nothing to borrow.
00:11:05 So if there's nothing that you can borrow the homology structure directly, what can you do? Right?
00:11:10 So we're going to revisit the principle and then again we're going to look at this problem
00:11:15 from the three elements of optimization. We're going to ask ourselves in this scenario
00:11:20 what is the corresponding formulation for optimization? What is the optimization formulation?
00:11:25 So these are the and in the end we're going to talk about the corresponding implications
00:11:32 because we need to design algorithms for this kind of problems. Right?
00:11:41 And we probably have more time to even start talking about numerical optimization
00:11:46 in this lecture. Okay? But we'll see. We'll start with the gradient based local search. Okay?
00:11:54 All right. These contents, today's twilight zone, ab initial methods, meaning starting from scratch,
00:12:02 you can find it in the Thomas Schlick's chapter eight. You can also find some details about the
00:12:10 the non-convex optimization algorithms I'm going to talk about on Thursday from this book called
00:12:16 Numerical Optimization. Again, both books can be accessible through library. We have a library interface.
00:12:24 You can browse the electronic copy freely. Okay? Okay, let's get started. Let's talk about
00:12:31 how this problem can be formulated as an optimization, right? When you have no, seemingly no data to borrow. But I have to
00:12:40 clarify that even in this midnight zone, you can use some data. Okay? So let's start. If right now there's no
00:12:50 homology data that I can use apparently, what can I do? Well, we have to follow the principle then.
00:12:58 What input leads to the output, right? So how can a one-dimensional sequence fold into a three-dimensional
00:13:04 structure? Again, we have learned this before. This is a energy minimum principle, right?
00:13:10 Discovered experimentally and verified experimentally by Enthamson, et cetera, who even before I was born. So
00:13:19 this statement is the following. The three-dimensional structure of the native protein is in its normal
00:13:26 physiological milieu. Okay? So the three-dimensional structure is the output we desire.
00:13:32 So it's corresponding to the one in which the Gibbs free energy of the whole system is the lowest.
00:13:40 Okay? So this whole system includes the protein, but it also includes its environment. This is actually a
00:13:46 case of the second law of thermodynamics. Okay? So if you have to solve this problem,
00:13:52 what is your next question?
00:13:58 How do I calculate the Gibbs free energy? Is that right? Yeah. Thanks. Okay? So let's see whether it's
00:14:03 something that we can easily calculate. Okay? So let's start with the objective function. We're going to talk
00:14:10 about the physics-based, but also knowledge-based, but like, for instance, data-based, right? So
00:14:18 these energy functions are going to be talked about first, then we're going to talk about the decision
00:14:22 variables. What's the dimensionality? How do you parameterize it? In the deep learning world,
00:14:29 the objective function is most likely learned. It's also knowledge-based, but it's mostly likely
00:14:36 a deep learning model learned from the data. In other words, it's an extension of the statistical
00:14:42 potential. Okay? And also in the deep learning world, the parameterization of the decision variable
00:14:48 is still critically important because that involves what kind of input you provide to the model, right?
00:14:56 Right? I know that we tend to think that deep learning models are universal functional approximators.
00:15:02 So if you're using the input-output pairs, it's as if you give any kind of input-output pairs,
00:15:05 we can find a deep learning model architecture. That is a very naive idea. Okay? So you can
00:15:13 parameterize the input-output to help or make this model or architecture development easier. Okay? So we can
00:15:22 talk about that later. And then there's a search algorithm involved as well. So let's talk about the
00:15:28 classical setting for the moment, and we'll talk about deep learning modules when we get there in a little bit
00:15:37 around two weeks. Okay?
00:15:40 So the Gibbs free energy, so the concept. Okay? We say that there is an unfolded protein sequence.
00:15:49 This is a backbone, like a string, right? Then it's folded into a three-dimensional structure,
00:15:57 right? So I ignore the secondary structures here. So from unfolded to folded, right? So the Gibbs free energy
00:16:05 is actually consisting of enthalpy and entropy. So, right, this H is, if you have learned thermodynamics in
00:16:14 your sophomore, you know that this is a Hormel's enthalpy, which includes U plus PV, where U is the
00:16:23 internal energy. Okay? And then there's also the entropy part, which is multiplied to the absolute
00:16:32 temperature. Okay? So H minus TS. That's a Gibbs free energy for the protein in any state. So you could
00:16:40 have the Gibbs free energy in the unfolded state or the folded state. So if you take the difference
00:16:47 of the Gibbs free energy between the unfolded and the folded states, then, you know, you get a delta G.
00:16:54 Delta indicates the difference. If the temperature is constant, then delta G equal to a delta H minus T
00:17:02 times delta S. Okay? So that is the change of the Gibbs free energy or the, you know, folding free
00:17:09 energy, Gibbs free energy. So this Gibbs folding free energy will be minimized. This will be minimized.
00:17:17 Okay? So this is the objective function. So this delta H is the change in the enthalpy. This includes what we have learned before, all these
00:17:27 bounded and non-bonded interactions that put proteins into its shape, right? But I don't know whether you
00:17:34 noticed before I was saying that the Gibbs free energy of the whole system, this includes the protein that's in the enthalpy part,
00:17:42 but there's also the environment like the water. So that's in the entropy. Okay? So we're going to talk more about it.
00:17:50 You have the protein, you have the environment, which is a solvent, and together, you get the whole system. Okay?
00:17:57 Then there is a, you know, when the protein is existing in different states, when X is corresponding to different values, we have to talk about what X is.
00:18:09 The corresponding Gibbs free energy delta G, right, will also tell you what's the probability distribution of that state of X.
00:18:21 In that case, is following the Boltzmann distribution, exponential to the minus delta G divided by RT.
00:18:28 This Boltzmann distribution will actually use the lot in computer science, right?
00:18:35 Starting from the simple example of Marco Chen onto Monte Carlo, you are using Boltzmann distribution.
00:18:41 Then there is the restricted Boltzmann machines, right? One of the early models of deep learning. So this Boltzmann distribution actually has these impacts far reaching beyond molecules.
00:18:53 Okay? So now let's talk about this enthalpy and entropy. Why we want to talk about it? We're still trying to figure out this problem.
00:19:02 Is it easy to minimize this function, right? So that's all we are trying to figure out, right?
00:19:07 Is it easy to minimize this function? Well, let's talk about it. This function, how to calculate this function, right? How to calculate this function, right?
00:19:18 That means you have to somehow, you know, for a given protein in some given state, right? All the atoms in different positions, you have to calculate its, you know, energy, right?
00:19:30 Enthalpy, entropy included. And that means that you have to parameterize the state of the molecules and have a mapping between the state and the energy values, right?
00:19:47 So the mapping is often called the force field. It's like, you know, if you put a protein in the force field, how you calculate the energy, okay?
00:19:57 So if we really have to solve the Gibbs free energy, okay, from the principle, what we know is that it starts from the Schrodinger equation, okay?
00:20:12 So in this case, you are considering each molecule as a set of nuclei and their electrons, right?
00:20:20 And the nuclei includes neutrons and protons and everything. And then this Schrodinger equation, right?
00:20:27 If you look at this one, this looks like what? This looks like AX equal to Lambda X, isn't it?
00:20:33 Right? AX equal to Lambda X means what in linear algebra?
00:20:39 Means Lambda is the eigenvalue of the matrix A. Is that right? Right?
00:20:46 So here is very similar, right? So you have H psi equal to E psi, right? And AX equal to Lambda X, right?
00:20:55 So in this case, this psi is the basis or basis functions, or these are the eigenvectors, right?
00:21:06 So these are like the eigenvectors. These are the wave functions or eigenvectors.
00:21:11 And the corresponding E is the eigenvalue of the Hamiltonian H, which is an operator, right?
00:21:20 And then it's, let's put it in this way, even given the current computers, it's really difficult even to calculate the Schrodinger equation for a very simple, like, multiple atom molecular system.
00:21:36 Not to mention the proteins we are talking about, okay? Even if you do some approximation, separate nuclei and electrons, right?
00:21:45 So this is, you know, this principle is useful, right? And we even know that we can solve the Schrodinger equations in principle, but this is almost, well, I'd say it's just intangible, given the current computers, okay?
00:22:01 So it's accurate, but intangible. So that means we have to do further approximations. That's what molecular mechanics is doing, okay?
00:22:13 So molecular mechanics is saying that, well, can we regard these, you know, molecules as if there are a lot of hard spheres, right?
00:22:22 Like atoms regarded as hard spheres, and then they are attracted to each other with some forces, right?
00:22:28 So we are regarding them by, like, a lot of hard spheres connected by the strings, right?
00:22:34 I'm sorry, the springs. And the molecule can stretch, can bend, and rotate about these bonds as if it's a mechanical body, right?
00:22:44 For instance, you have two atoms connected, one and two, then along this direction is like a hook-in potential, right?
00:22:54 So when they are close, they are pushed away. When they are far away, they are attracted to each other.
00:22:59 Then there is a one, two, three, three atom mechanics.
00:23:03 Then when you fix the atom two, but, you know, you can change the angle formed between atom one and atom three, then that is, you know, angular potential.
00:23:17 Or if you look at atom one, two, three, four, all connected with each other, and then there is a torsional angle, right?
00:23:24 Torsional angle here between two and three, then it's as if you can rotate around this torsional angle.
00:23:30 So all this can be regarded as molecular mechanics.
00:23:37 So there is one, two stretching, one, two, three angle bending, and one, two, three, four torsional rotating.
00:23:45 Then you can often, then you ask, if I stretch this bond by, like, one-tenth of an atom, how much does the energy change, right?
00:23:54 So those parameters, right, those parameters are often derived empirically.
00:24:00 So in other words, in early days, what is this like?
00:24:04 It's also data science, just not that much data driven.
00:24:09 In other words, it started with the principle, we want to treat these force fields as if, you know, they are like molecular mechanics.
00:24:19 Then we have some principles, right?
00:24:21 Like, you know, the Hukum potential, which is quadratic in the change of the distance, right?
00:24:26 And then we have all these force fields calculated, right, for a protein or a molecule, actually, at the very beginning, very simple molecules, right?
00:24:37 And then we calculate them in different, based on our force field, and we compare the values experimentally observed.
00:24:46 Then we can fit those parameters.
00:24:50 Is that right?
00:24:51 So in other words, it's just the early days data learning, except that the models are extremely simple, not like deep learning.
00:24:58 It's just quadratic, for instance.
00:25:00 And then, you know, the data is very small.
00:25:03 It's not big data, right?
00:25:05 You may have maybe 50 molecules, experimental measurement at different conditions.
00:25:10 And that was already just, you know, fitting that few parameters, okay?
00:25:14 And this works well.
00:25:17 Molecular mechanics works well for most of the cases, except if you have to talk about breaking a bond or forming a bond.
00:25:26 Because in our case, we can, you know, we can stretch or bend, but we cannot break those bonds, okay?
00:25:32 So that's what molecular mechanics can deal with.
00:25:35 But once you break or form a bond, like, you know, enzymes make the chemical reactions much faster, right?
00:25:41 So in those cases, they actually break and form bonds, and that you have to deal with using quantum mechanics.
00:25:49 So in this case, if we don't have to deal with bond breaking or forming, we can use molecular mechanics.
00:25:56 It's not as accurate, but it's now tangible.
00:25:59 It's now tangible, okay?
00:26:02 So what, of course, you can get the best of both worlds, right?
00:26:06 Actually, that led to the Nobel Prize in chemistry 2013.
00:26:11 So this is actually three chemists, three computational chemists, who develop the force field, which can interface the quantum mechanics and the molecular mechanics.
00:26:24 It's basically saying that, you know, in this very small region where the protein is forming or breaking bonds, we treat them with the quantum mechanics.
00:26:35 In the bulk region of the protein that does not involve bond breaking or forming, we treat them as the classical physics, that's the molecular mechanics.
00:26:45 Then the issue is how do you deal with the interface?
00:26:50 So that's a, you know, classical mesoscale modeling problem, right?
00:26:55 Because you have different scales, you have to bridge them.
00:26:58 And that is the one getting the best of both worlds.
00:27:05 But I want you to notice that Michael Levitt, who is now at Stanford, some of the slides we're going to show you, including one I showed last time for the threading when you align a sequence to the fold.
00:27:18 I don't know whether you noticed the special fonts.
00:27:21 That font was actually developed by Michael Levitt as well.
00:27:25 One of his accomplishments, but of course, very, you know, far from the top of the contributions.
00:27:34 And this is one of his contributions, top contributions.
00:27:38 Okay.
00:27:39 So now let's talk about molecular mechanics alone.
00:27:42 So what is it like?
00:27:43 So this is the, what you see here is the fonts created by Michael Levitt.
00:27:50 It's very close to how he write manually.
00:27:53 Okay.
00:27:54 So as I said that the molecular mechanics force field of a molecule is a sum of a lot of atomic interactions.
00:28:04 Okay.
00:28:04 So there is one, two interaction involving two proteins, excuse me, involving two atoms.
00:28:11 So in this case is we are looking at all bonds.
00:28:14 And if this bond length is deviating from the equilibrium B naught, then we have a quadratic penalty.
00:28:22 And this penalty is proportional to K sub B, which is bond specific.
00:28:28 Again, this parameter K sub B is bond specific and estimated from experimental data.
00:28:33 Then we have all these one, two, three interactions, right, involving three atoms.
00:28:39 In other words, the angle, right, is changing.
00:28:43 Again, this is a, you know, quadratic penalty around the equilibrium.
00:28:48 Then there is a torsional angles, which is more sinusoidal, right?
00:28:52 And then these are the bonded interactions.
00:28:56 And then there are non-bonded interactions.
00:28:57 As we said before, there is a Van der Waals interactions that includes the r to the power of 12 minus 12.
00:29:06 That's a repulsion, right?
00:29:08 That's dominating the repulsion.
00:29:10 And there is a r to the power of minus 6.
00:29:13 That's dominating the attraction.
00:29:14 And they together determine a optimum distance, right?
00:29:19 It's like, as I said, there is an ideal distance between the two atoms.
00:29:28 And then there is also Coulombic electrostatics.
00:29:31 That's just the QI times QJ, the two charges divided by r.
00:29:35 And then there is, you have to sum all these calculations over all the bonds, all angles, all torsional angles, all non-bonded pairs, and all partial charges.
00:29:47 So in other words, it's like a pairwise decomposition.
00:29:51 You have to look at all the atom pairs, right, and then calculate these bonded and non-bonded interactions and add them together.
00:29:57 So if you think about 1,000, or let's say 100 amino acids, and each amino acid has about, let's say, 10.
00:30:07 Okay, it's way more than that.
00:30:09 Then you have 1,000 atoms.
00:30:10 And then to calculate the energy of a protein with 1,000 atoms, right, in any state X, we have to do what?
00:30:21 1,000 choose 2.
00:30:24 Pairwise calculations, right?
00:30:27 And for each pair, 1,000 choose 2 pair, we have to calculate the 1, 2, 3, 4, 5.
00:30:33 Five kind of terms, right?
00:30:35 So that's very expensive, but better than Schrodinger's equation.
00:30:41 So without more details, you know, those of you who are interested in why these Vandervauss interactions or, you know, Coulombic interactions are calculated in this way,
00:30:54 you can look into these slides and additional contents, okay?
00:31:01 And this is the two non-bonded interactions, okay?
00:31:05 So far, I have talked about the bonded and non-bonded interactions that gives you the enthalpy, which only depends on the protein.
00:31:14 But I haven't talked about the entropy yet, right?
00:31:17 So entropy is like, what is entropy describing?
00:31:26 It's describing how ordered a system is, right?
00:31:31 Right?
00:31:31 So when you first move into your dorm, right, it's very ordered.
00:31:37 After a semester, your dormitory gets very disordered.
00:31:41 So that's actually following the second law of thermodynamics of entropy maximization, actually.
00:31:49 Okay, that's a joke.
00:31:50 So the entropy part is exactly talking about the environment effects.
00:31:57 It's talking about, you know, these hydrophobic effects, right?
00:32:02 So that's hydrophobic effects is like, you know, those residues that don't like water and they like to mingle with each other and hide in the core from the water, right?
00:32:12 So there's these hydrophobic effects.
00:32:15 That's usually calculated by the change in the solvent accessible surface area.
00:32:21 So if the surface area accessible to the solvent is changed by some amount, then the hydrophobic effects is just measured by a linear function in that change of the area.
00:32:32 But then there is a solvation.
00:32:34 You know, that's, as I said, when you hide a residue or atom in the core of a protein, right, in the folded state,
00:32:45 compared to the unfolded state, it, of course, gained some new interactions.
00:32:52 It gained some new interactions within the core, right?
00:32:56 But it also lost interactions with waters because it's hidden from the waters now.
00:33:04 So this is called a desolvation.
00:33:06 So, yeah, so you are gaining the water screened electrostatics, right?
00:33:12 But you are also losing the interaction with waters.
00:33:14 So that's a desolvation.
00:33:16 So this model to calculate the, you know, environment effect is often called MMPBSA.
00:33:23 Well, MMP is calculating the hydrophobic effect.
00:33:28 And then Poisson-Balsman, I'm sorry, excuse me, MMP is calculating the enthalpy as I described before.
00:33:35 Then Poisson-Balsman is calculating the solvation, right?
00:33:39 And then SA is for the solvent accessibility for calculating the hydrophobic effects.
00:33:45 So there are different programs like Charm or Amber that can calculate the energy values if you give a protein structure to it.
00:33:54 So this is the objective function.
00:33:58 Any question about the objective function so far?
00:34:00 So now let's talk about the decision variables, okay?
00:34:07 So in the end, I'm going to ask you what does the objective function tell us for solving the optimization problem, okay?
00:34:20 Because that's why you're interested in how to calculate the objective function, right?
00:34:25 So I gave you some hints before, including the fact that we're calculating the energy function over many pairs, right?
00:34:33 So that gives you some hint about the challenges.
00:34:37 Next, we're going to talk about decision variables, okay?
00:34:40 Let's bear that question in mind and move on to the decision variables.
00:34:43 So first, let's talk about the dimensionality, right?
00:34:48 So if we have a molecule of capital N atoms, right?
00:34:53 And these N atoms are not linear, okay?
00:34:56 So they are not on a line.
00:35:00 And the conformational space or, you know, it's another word of saying that the structural space, okay?
00:35:07 So the conformational space of the molecule has how many degrees of freedoms?
00:35:25 Anyone?
00:35:29 N degrees of freedoms?
00:35:31 How many degrees of freedoms are there for each atom?
00:35:37 For each atom?
00:35:45 Three.
00:35:45 Three.
00:35:46 So is it three times N?
00:35:57 Okay, so can you repeat again, Doyang?
00:36:01 Yeah.
00:36:02 So the rotation angle and the distance between atoms should be paralyzed things?
00:36:11 So maybe you can divide it by two.
00:36:15 I see.
00:36:15 So you are seeing some redundancy if we consider all the three times N that we're trying to say.
00:36:20 I'm not sure that we are dividing that by two because I think the only degrees of freedoms we considered redundantly, right, was probably, you know, everything moving together as a rigid body.
00:36:41 Three rotations and three translations.
00:36:44 Do you see what I mean?
00:36:45 So if this is one configuration, it doesn't matter whether I rotate or translate.
00:36:51 This is still the same configuration.
00:36:53 Do you see what I mean?
00:36:54 So in other words, yes, in total there are three times N, but I don't care about their collective rigid body motion, which has six degrees of freedoms.
00:37:05 So in total there's three N minus six degrees of freedoms.
00:37:09 All right?
00:37:10 Okay, so that's one thing.
00:37:12 So, of course, you know, the dimensionality of the space, of the search space is one thing, but how you parameterize the search space is another thing.
00:37:24 It's not like, you know, it's not like it's always ideal to parameterize your search space so that it's matching the degrees of freedoms, right?
00:37:33 Because it may sound economic, but it may give you a hard time optimizing, okay?
00:37:38 So, for instance, you could parameterize the search space using three times N partition coordinates, even though you know that you have six redundant ones there.
00:37:51 This is the most convenient way, and it's kind of natural when you do the molecular dynamics because you need to figure out where each atom is at any time point
00:38:05 and then calculate the forces and the potentials on each atom and atom pair and sum them together.
00:38:13 However, however, remember, we are talking about proteins who are not ideal gas.
00:38:21 So these N atoms are actually dependent of each other, their positions, right?
00:38:29 Because of the bounded and non-bounded interactions.
00:38:32 So in other words, in this 3N minus 6 dimensional space, there are additional constraints, right?
00:38:40 Right?
00:38:42 Couplings among the degrees of freedoms.
00:38:45 So in other words, we're not talking about R3N minus 6, right?
00:38:50 We're talking about, as I said before, as if you have to look at all the small islands on the Pacific because those are allowed combinations of the positions.
00:39:02 You see what I mean?
00:39:03 If you're talking about two-dimensional space, right?
00:39:06 It's not like all the Pacific, right?
00:39:10 But only those islands which satisfy the constraints, right?
00:39:15 Because you cannot break the bounds freely.
00:39:19 You cannot stretch the bounds freely, right?
00:39:25 Okay, so this is Cartesian coordinates.
00:39:28 So it's actually very convenient and natural, but you have to consider the constraints.
00:39:32 So that's one thing, okay?
00:39:35 Another one is the internal coordinates.
00:39:39 In the case of internal coordinates, we actually have addressed this before when we do the Ramachandran plot,
00:39:45 if you remember.
00:39:46 We say that we can consider the bound lengths, bound angles, and dihedral.
00:39:50 In that case, bound lengths and bound angles can be regarded fixed, right?
00:39:55 So in this case, we can also use the internal coordinates by explicitly considering those constraints.
00:40:02 We can say that, well, we can have the bound lengths and the bound angles, right?
00:40:06 They could be neglected if fixed.
00:40:09 Then we can talk about the dihedral.
00:40:11 Okay?
00:40:11 And then the dihedral can be parametrized using Euler angles or quaternions and so on.
00:40:19 But quaternions would be an easier way to get derivatives if you need it, actually.
00:40:26 I mean, I've been talking about this all the time, and it's great to see that AlphaFold is exactly following this as well,
00:40:33 using the quaternions to parametrize the dihedral.
00:40:38 And again, I want you to think about this parametrization because this is critically important also in the deep learning world.
00:40:49 Again, how you represent, right?
00:40:53 I say parametrize in the world of optimization, but how do you represent the input in the world of machine learning is critically important to the choice of the architectures and effectiveness of the model architecture you're talking about.
00:41:08 Okay?
00:41:08 And there are other parametrization that can reduce the dimensionality, right?
00:41:15 To alleviate the curse of dimensionality.
00:41:19 For instance, the sidechain confirmations can be discretized, right?
00:41:24 So if you have watched the movie Matrix, have you seen this Montage shot, a slow motion showing how Neo is dodging the bullet?
00:41:41 Did you see that?
00:41:42 Right?
00:41:43 So if you think about Neo as a sidechain, which has a lot of continuous flexibility, right?
00:41:49 But you could discretize that continuous flexibility into the discrete snapshots, right?
00:41:58 Right?
00:41:59 Actually, that is good because what?
00:42:01 You don't consider all these atoms or joints separately.
00:42:06 You consider them collectively, isn't it?
00:42:08 Because every snapshot is reflecting a collective motion of all atoms of the body, isn't it?
00:42:15 So that's what the discretization is doing in the case of the sidechain, okay?
00:42:21 So it's like different snapshots or different combinations of proportional angles, okay?
00:42:27 Which are observed statistically, right?
00:42:30 Or calculated.
00:42:32 So these are the conformational variables.
00:42:35 Lastly, let's talk about the search algorithm, right?
00:42:39 So based on what we have talked about for objective function and the decision variable,
00:42:43 what can you say about the search algorithm?
00:42:46 Do we need a search algorithm?
00:42:49 I think we do, right?
00:42:54 But what are the challenges based on what you have learned about objective function and decision variables?
00:43:01 Any challenges?
00:43:02 Any challenges?
00:43:13 First of all, is this an easy problem?
00:43:15 Is this convex optimization?
00:43:21 It's probably very non-convex, judging by, first of all, the objective function.
00:43:26 Right?
00:43:27 Even if we can parameterize the search space using the internal coordinates, right?
00:43:32 So it's a non-convex optimization problem.
00:43:35 The objective function is non-convex and the decision variable defined feasible space can be convex depending on the parameterization.
00:43:45 So, but there are way more challenges, right?
00:43:49 So I said it's non-convex.
00:43:51 There are a lot of local minima.
00:43:53 But also there's a non-smooth issue.
00:43:57 In other words, the derivatives can be discontinuous.
00:44:01 Why?
00:44:01 Because if you remember, we had to calculate the van der Waals, electrostatics, and everything for all pairs of atoms.
00:44:12 For all pairs of atoms.
00:44:13 Which is computationally unfavorable.
00:44:16 So, so in practice, people sort of look at a cutoff distance and say that, well, if these two atoms are within this cut, whose distance is within the cutoff, then I'm going to calculate the force.
00:44:30 Otherwise, I'm just going to regard it as zero.
00:44:33 Right?
00:44:33 But then you realize that, oh, then that's a problem because if you look at this dashed line, which is calculating the van der Waals, right, for two atoms until reaching the cutoff.
00:44:51 So at the cutoff distance, we see a non-smoothness.
00:44:56 The derivatives are not continuous.
00:44:58 So that's a problem.
00:44:59 So what people usually do is actually smoothing these van der Waals probably, right, or truncate, smoothing these truncated ones.
00:45:08 But this is one challenges if you want to use gradients, okay.
00:45:14 And also this energy function is very costly to evaluate for a given confirmation because you have to sum over many atom groups.
00:45:24 Even if you are just talking about atoms within some distance, you are still talking about a lot of atom groups.
00:45:31 And if the energy function is expensive, the derivatives are even more expensive because one is the zeroes order information, one is the first order information.
00:45:40 So in other words, this is an energy minimization problem for which you don't want to evaluate f of x at too many x because evaluating f of x is extremely expensive.
00:45:55 So you want to save your budget of evaluation.
00:45:58 Okay, so that's one challenge.
00:45:59 What about the other challenge?
00:46:03 I said before that it's not just the f of x.
00:46:06 It's non-convex and expensive.
00:46:09 x is very highly dimensional and highly coupled, right.
00:46:13 And there could be a mixture of continuous and discrete.
00:46:17 Then one thing we haven't paid attention is because I told you that there's different bounded and non-bounded interactions,
00:46:27 but I haven't told you what they may be dominating at.
00:46:32 Okay.
00:46:33 They actually can bring the opportunities.
00:46:36 So there are some energy terms like Van der Waals which are high frequency,
00:46:41 meaning that a tiny change of x can result in a huge change in f of x.
00:46:48 So remember f of x is a sum of different terms, and each term is calculated over different pairs.
00:46:55 So for some terms, like Van der Waals is talking about the shape complementarity.
00:47:01 So if you have this kind of optimum configuration of atoms, if I move by just one tiny bit,
00:47:10 then fingers or atoms run into each other, then that's a huge clash, isn't it?
00:47:15 So if I move x a tiny bit, the Van der Waals portion of f of x change drastically and create those peaks in the energy landscape.
00:47:28 So that's one issue that we have to deal with.
00:47:32 So these short-range terms can be minimized using gradient-based algorithms very easily.
00:47:38 So this is actually what people do at the final stage of homology modeling in the safe zone.
00:47:46 All right.
00:47:46 The bigger problem is the other terms, which are of lower frequency.
00:47:52 That means they don't change that drastically with regard to the change of x.
00:47:59 So in those cases, the longer-range energy terms actually dominate the global landscape.
00:48:07 So you have a lot of peaks created by these short-range terms like Van der Waals,
00:48:13 but the global shape is determined by the lower frequency terms like dissolvation or electrostatics and so on.
00:48:23 So in those cases, the global shape is critically important to global optimization.
00:48:32 However, gradient can only tell you the local information.
00:48:37 Is that right?
00:48:38 Right?
00:48:38 So gradient can tell you at every position what's a dimp or bump like on the way from here to Houston.
00:48:47 Right?
00:48:47 At every point, it tells you the local dimp or bump.
00:48:51 But it doesn't tell you the global shape.
00:48:54 Right?
00:48:54 Right?
00:48:55 And the global shape is actually more important for the global optimization.
00:48:59 So these are the challenges, but also give you the opportunity of some early methods.
00:49:04 Right?
00:49:06 So some of the early methods actually try to disregard the short-range terms and focus on the longer-range terms,
00:49:18 and then smooth the landscape and focus on the global landscape.
00:49:23 Okay?
00:49:23 So that's how this knowledge of the system inspired the algorithms.
00:49:31 Okay?
00:49:31 So next, we'll start with the gradient-based algorithms, because I said they're not that useful for the global optimization,
00:49:41 but it can remove the clashes, which are like Vanderville's terms.
00:49:47 Okay?
00:49:47 So if unfavorable Vanderville's like clashes, they can be removed or refined.
00:49:53 Okay?
00:49:54 Those can still be done with gradient-based algorithms.
00:49:57 So I'm going to talk about the gradient-based algorithms.
00:49:59 But then I'm going to also talk about the gradient-free algorithms, because A, the local gradients are not that useful for global optimization.
00:50:11 Not to mention that they're expensive.
00:50:13 Okay?
00:50:14 The local gradients are expensive, but yet informative for the global optimization.
00:50:19 So you have to somehow figure that out using some gradient-free algorithms.
00:50:23 So I will start with the gradient-based algorithms.
00:50:27 And so let's wrap up this portion.
00:50:34 So we basically look at this protein structure prediction problem now in the midnight zone.
00:50:42 The approach is ab-initial, meaning starting from scratch.
00:50:45 We had to ask a few questions, starting with the principle we can start with.
00:50:51 As the data, homology data, is not revealing enough.
00:50:55 And we sort of looked at this problem again from the formulation of optimization.
00:51:00 We asked, what's the objective function like?
00:51:03 What's the search space like?
00:51:06 Is there a need of search algorithms?
00:51:09 Right?
00:51:09 And then what are the implications from the objective function and the search space tell us in the design of optimization algorithms or search algorithms?
00:51:20 Okay?
00:51:20 We now know that we probably shouldn't rely on gradient-based algorithms if you want to solve these global optimization problems.
00:51:28 Right?
00:51:28 Because you will be painfully spending lots of time just jumping up and down the local terrains without being able to move too far away.
00:51:43 Right?
00:51:43 So that's a problem.
00:51:46 Nevertheless, let's start with the gradient-based algorithms.
00:51:53 Okay?
00:51:53 Any questions so far?
00:52:04 So we are talking about numerical optimization.
00:52:09 Okay?
00:52:09 Which is in comparison to analytical optimization.
00:52:15 Right?
00:52:15 For instance, if you are just solving a quadratic functions optimization problem, you know analytically where the global optimum of that quadratic function is if the Hessian is convex.
00:52:27 You know where exactly it is.
00:52:29 Right?
00:52:29 So in that case, we can analytically solve the optimization problem.
00:52:33 But sometimes you have to solve it numerically.
00:52:36 So that's in that sense, we are talking about numerical optimization.
00:52:41 So the contents can be seen in the Thomas Schlich's book chapter 11 as well as the book called numerical optimization.
00:52:52 Again, both electronic copies are freely accessible through our university's library.
00:52:58 Okay?
00:53:00 So we are going to talk about non-convex numerical optimization.
00:53:05 And we start with gradient-based local search.
00:53:08 Okay?
00:53:08 We are going to talk about the basic concepts and give you some introductions about different kind of gradient-based algorithms.
00:53:15 But also I want you not to just, you know, know these different gradient-based algorithms for the sake of knowing.
00:53:25 I want you to think about it as if you were to design these gradient-based algorithms.
00:53:32 Right?
00:53:33 So how would you approach this problem?
00:53:36 How would you start with some earlier versions and introduce algorithmic innovation and develop something better?
00:53:45 In what sense?
00:53:46 These are the questions I'm trying to ask.
00:53:49 Okay?
00:53:50 So let's keep that in mind.
00:53:52 We'll start with, again, we're in the midnight zone.
00:53:56 We'll start with the gradient-based algorithm.
00:53:58 I said that, you know, they're at least useful for the short-range energy terms.
00:54:03 For instance, we want to remove the clashes of two atoms or a lot of atoms.
00:54:08 Right?
00:54:09 Those are dominated by the short-range energy terms.
00:54:14 Okay?
00:54:14 It's a very local optimization.
00:54:17 So gradient-based optimization.
00:54:21 So a few concepts.
00:54:23 As a reminder, you have learned this before.
00:54:26 We focus on unconstrained optimization for the moment without any constraints on X.
00:54:32 For the moment.
00:54:33 Okay?
00:54:33 So you can rewrite a constrained optimization into unconstrained using Lagrangians.
00:54:39 And for those of you who have learned it, please review the concepts.
00:54:43 If you haven't, please look into the numerical optimization book and look at Lagrangians.
00:54:49 Okay?
00:54:49 The chapter of constrained optimization.
00:54:51 So we focus on unconstrained optimization for the moment.
00:54:55 And we are also talking about large-scale unconstrained optimization for the moment where X is very high dimensional.
00:55:02 Okay?
00:55:03 Later on, we'll talk about when X is even higher dimensional.
00:55:07 Right?
00:55:08 For instance, parameters of an over-parametrized deep learning model.
00:55:12 So in those cases, many of you have already learned, for instance, stochastic gradient algorithms.
00:55:18 Right?
00:55:18 But let's talk about gradients, for instance.
00:55:23 Right?
00:55:23 So we are interested in, now, local optimum.
00:55:28 Okay?
00:55:28 So local optimum.
00:55:29 So there's a related concept called stationary point.
00:55:33 Which is saying that the gradient G of X, which is the, you know, the partial derivatives.
00:55:40 The vector of the partial derivatives.
00:55:42 Right?
00:55:43 Is equal to a zero vector.
00:55:44 So if the gradient is zero at a point X, then that X is called a stationary point.
00:55:55 Okay?
00:55:56 For that function F of X.
00:55:58 This stationary point, if we look at a one dimensional example or illustration, this stationary point could be a local minimum, could be a local maximum, could be a saddle point.
00:56:13 Okay?
00:56:13 So in the one dimensional case, saddle point means that it looks like local minimum going from one direction, but it looks like local minimum going from the other direction.
00:56:22 In the two dimensional space, you can see clearly why it's called a saddle point.
00:56:29 Because if we look at this function along the two dimensions, X and Y, or X1 and X2, we see that this point is the local maximum along the X dimension.
00:56:44 And it's a local minimum along the Y dimension.
00:56:48 So it, so this contour looks exactly like a saddle, right?
00:56:53 So that's why it's called a saddle point.
00:56:56 Okay?
00:56:58 So in deep learning, when you are developing these non-convex optimization algorithms for training deep learning models, one of the biggest issues is how to not be trapped at saddle points.
00:57:13 Okay?
00:57:13 You know, this is just a two dimensional.
00:57:16 Now imagine that you're over parametrized transformers.
00:57:19 How many dimensions you have?
00:57:21 How many saddle points you would have in that high dimensional space?
00:57:26 So now, as we said, some of the stationary points are local minimum that we are interested in.
00:57:32 Okay?
00:57:33 So in the case of the local minimum, first, it's a stationary point.
00:57:38 So the gradient has to be zero.
00:57:41 But also, not all stationary points are local minimum.
00:57:45 So which ones are?
00:57:47 They're a Hessian, which is the second order derivatives.
00:57:52 Okay?
00:57:53 Is positive semi-definite.
00:57:57 So it's, you know, non-concave.
00:57:59 Okay?
00:58:01 So the shape is like convex.
00:58:04 So this is what a local minimum is.
00:58:07 Okay?
00:58:09 Any questions so far?
00:58:11 Okay.
00:58:12 So this is a review.
00:58:13 So now, let's talk about how to find the local minimum.
00:58:19 Okay?
00:58:19 So let's first look at a very simple example, which is a quadratic function.
00:58:26 Where x, again, is a vector and A is a matrix.
00:58:30 So you have the quadratic term and the linear term.
00:58:33 Okay?
00:58:35 So what is the gradient of this function, Qx?
00:58:42 I know that it's very easy if we calculate the gradient if x is a scalar.
00:58:56 Okay?
00:58:56 So you've got to be comfortable with this linear algebra.
00:59:00 When x is a vector, how we calculate the derivative.
00:59:05 Okay?
00:59:07 Any...
00:59:08 Anyone want to try?
00:59:19 Okay.
00:59:20 Let's look at the simpler problem.
00:59:22 If there's no quadratic term, there's only B transpose x.
00:59:26 What's the gradient of Q of x with regard to x?
00:59:31 Just the B, which is a column vector, right?
00:59:40 Okay.
00:59:41 So in this case, the quadratic term, what's the derivative?
00:59:52 Gradient, I'm sorry.
00:59:53 Okay.
01:00:00 2Ax?
01:00:01 Is that right?
01:00:02 Okay.
01:00:02 Good.
01:00:03 So the next question is, what's a Hessian?
01:00:06 It's simpler.
01:00:07 What's a Hessian of Q of x?
01:00:12 2A?
01:00:13 Right.
01:00:14 Yeah.
01:00:14 So, okay.
01:00:15 So sometimes people put a one-half in front of the quadratic term
01:00:19 so that the Hessian is just A.
01:00:21 Okay.
01:00:21 So now let's say let's look at A.
01:00:24 Okay.
01:00:25 So depending on the Hessian matrix, okay, if we look at a two-dimensional illustration,
01:00:34 this landscape or the shape of a Q of x, right, can be very different.
01:00:40 Right?
01:00:40 So for instance, if A is positive definite, right, then you have a convex shape, right,
01:00:49 along, you know, all the dimensions or in the joint two-dimensional space.
01:00:55 So then you have a, you know, local and global optimum here.
01:01:01 If you have a that is a negative definite, so it's concave shape instead, so there is a local and global maximum, right?
01:01:12 If A is positive semi-definite, right, if A is positive semi-definite, right, in that case, what do you see?
01:01:27 That means along some dimension I have a convex shape like this, but along some other dimension I have a constant curvature,
01:01:38 like what you see here, this line, right?
01:01:41 Because the eigenvalues are basically telling you how soon or how steep you climb up or down along that direction.
01:01:52 What direction?
01:01:53 Along the direction of the corresponding eigenvector, isn't it?
01:01:57 Right?
01:01:58 Right?
01:01:58 So in other words, if the eigenvector, there are two eigenvectors in this case, right, there is this one and the one perpendicular to it, right?
01:02:08 So along each eigenvector, we can even see clearly, oh, this is a convex function, so the lambda must be along that eigenvector,
01:02:18 corresponding to that eigenvector must be positive, and then this is a flat curvature, so the eigenvalue along this eigenvector,
01:02:26 corresponding to this eigenvector, must be zero, okay?
01:02:31 Of course, you could have a negative semi-definite, right?
01:02:37 Then you would just take, look at this one upside down, okay?
01:02:41 It's still singular.
01:02:43 And lastly, you have the indefinite cases where some eigenvalues are positive, some are negative,
01:02:51 so then it's exactly like what you see before.
01:02:54 You have a lot of subtle points.
01:02:56 The matrix is called indefinite, and you can see that there are a lot of subtle points along some eigenvectors.
01:03:03 You can clearly see that this point is local maximum, but along the perpendicular direction is the local minimum, okay?
01:03:13 So this is the illustration.
01:03:17 So now you are looking at the 3D curves and the meshes, okay, where the lines correspond to, you know, function values being identical, okay?
01:03:29 Now let's imagine that we look at these 3D curves or meshes from the, you know, from the top view.
01:03:40 Let's look top down, okay?
01:03:41 Let's look from the top and just look at the two-dimensional space because what I'm showing here is X is in two-dimensional space,
01:03:50 and the Z axis is actually the function value, right?
01:03:54 Now let's look from the top and let's look at this view.
01:04:01 Let's look from here and look down.
01:04:04 Then we are looking at a two-dimensional space of X alone, right?
01:04:09 Then we are looking at these so-called 2D contours, right?
01:04:12 Again, each line is corresponding to those points in X space that have the same function value.
01:04:22 For instance, here, this is corresponding to the indefinite landscape.
01:04:27 So we have the values here, for instance, 2, 6, 8, minus 1.
01:04:32 That means points on this line all have the same function values, okay?
01:04:37 So we need to be comfortable analyzing the 2D contours because we're going to use it later on,
01:04:45 illustrating the optimization algorithms, okay?
01:04:48 So here you look from the top, you see a lot of ellipsoids, right?
01:04:53 In the case of the convex or concave shapes, okay?
01:04:58 So the difference lies in whether the middle is of the lowest function value or the highest function value, okay?
01:05:10 So, and then this is a singular.
01:05:14 Again, if you look at it, it seems like there are a lot of lines, okay?
01:05:19 Any question so far?
01:05:21 Okay, so now let's start with...
01:05:24 Yes?
01:05:25 Will there be any scenario where second derivative will get defined?
01:05:32 Yes, you could have cases where the second order derivatives can be undefined somewhere.
01:05:40 It could be.
01:05:42 Yes?
01:05:42 If that's the case, then, in non-linear parameters, there are, like,
01:05:49 endowed on the other, so that one goes in that case.
01:05:56 Yes.
01:05:57 So if the gradients or the gradients of the gradient are not defined,
01:06:01 then in those cases, you have to use other approaches, right?
01:06:06 All right?
01:06:06 You could relax the definition of gradients using some numerical gradients,
01:06:11 or even the conceptually, you could use subgradients, right?
01:06:15 So there are alternatives.
01:06:17 Yes?
01:06:18 So in that case, you won't use Newton's method?
01:06:21 Whether you would use Newton's method or not.
01:06:23 First of all, Newton's method only uses gradients.
01:06:26 So if your gradients are defined in the search space,
01:06:29 you can use Newton's methods.
01:06:30 If you are talking about that Newton's method,
01:06:35 which also needs the Hessian,
01:06:38 then you need the Hessian to be defined.
01:06:41 Yes.
01:06:46 Good question.
01:06:47 So any other questions?
01:06:52 Then let's talk about what the optimization algorithm
01:06:59 needs to satisfy.
01:07:04 So what kind of algorithms do you want, right?
01:07:07 So you could have preference of local versus global optimum.
01:07:12 If you just want to remove clashes and refine the homology models,
01:07:17 then local optimization might be enough.
01:07:20 So your local minimum may be enough.
01:07:22 But if we look at a two-dimensional illustration
01:07:25 of the search space for protein folding problem,
01:07:28 then what you see is that the z-axis is energy
01:07:32 and the xy is configuration or confirmation of space.
01:07:36 It's just illustration, right?
01:07:38 Then you see that there is a very bumpy funnel, right?
01:07:42 So this is a very famous funnel-like energy landscape theory.
01:07:49 Then you can see that even though locally there are a lot of up and downs
01:07:54 and local minimums, which are intermediate protein structures,
01:07:58 which could correspond to misfolded proteins and diseases, right?
01:08:04 But there is a global optimum corresponding to the native protein structures.
01:08:10 So actually why people propose these energy landscape funnel-like landscape theory
01:08:19 was coming from a very simple idea.
01:08:24 Imagine that there is no global landscape that can funnel all the unfolded proteins
01:08:31 to the native folded protein structures.
01:08:35 Then you are basically looking at a flat landscape with holes here and then there, right?
01:08:43 Then it will take a protein forever to fold into its three-dimensional shape, right?
01:08:50 In this case, proteins can be folded very quickly because no matter where you are,
01:08:54 at the rim of the funnel, that is, no matter what structures unfolded proteins take,
01:09:01 you will glide down to the global optimum very quickly in nature, okay?
01:09:08 In algorithms, of course, it's different because nature can sample each x very quickly.
01:09:15 In computers, for each x, the calculation of f of x takes a lot of time.
01:09:21 So that's a difference.
01:09:22 But still, if nature had to try every possible x in a very flat, non-funnel-like landscape,
01:09:31 then it will take a protein forever to fold, okay?
01:09:36 So the other consideration is the convergence.
01:09:42 You remember we talk about what we care about, optimization algorithm.
01:09:46 We care about the accuracy.
01:09:48 We care about the complexity.
01:09:50 We care about the robustness.
01:09:52 So this is the theoretical concept corresponding to accuracy, okay?
01:09:58 So the accuracy is called convergence, okay?
01:10:04 So first of all, we have to make sure that when we keep running this, you know,
01:10:08 in this case, it's a numerical optimization algorithm that's iterative.
01:10:12 So we start with x0, then we somehow use some algorithm to generate a sequence x sub k,
01:10:20 following some updated rules.
01:10:23 And we are asking as k goes to infinity, right, asymptotically, could our optimization algorithm,
01:10:32 in other words, the sequence, eventually converge to the local minimum x star, okay?
01:10:38 So that's what the convergence means.
01:10:41 So whether your algorithms, in this case, iterative optimizers, would be accurate enough
01:10:48 so that at least when we have infinite resources and keep running it,
01:10:53 it will go to the global or local minimum, okay?
01:10:56 But you could have different iterative methods, all converging.
01:11:03 Some can be faster and some can be slower.
01:11:06 So that's the second concept.
01:11:08 That's called the convergence ratio or convergence rate, okay?
01:11:13 So the convergence rate says the following.
01:11:16 Let's look at the distance between the current steps sample and the global optimum, okay?
01:11:25 And then compare this distance to the last step sample's distance to the global optimum to the power of p, okay?
01:11:35 So we're calculating the distance to the global optimum in two consecutive steps, okay?
01:11:43 The future versus the present or the present versus the past, okay?
01:11:50 If this limit, as k goes to infinity, is between zero and a finite beta,
01:12:00 it has to be positive for sure because we have distances, right?
01:12:04 But this beta has to be finite.
01:12:06 If that is the case, then we say that, you know,
01:12:10 this optimizer is of convergence, of some kind of convergence rate.
01:12:21 For instance, if p equal to one, we say,
01:12:25 if p equals to one, I think it's easier to start with p equal to two.
01:12:32 If p equal to two, we call this algorithm with quadratic convergence, where p equals to two.
01:12:40 If p equals to one, we have to look at whether beta is zero or non-zero, okay?
01:12:47 So beta is non-zero and less than one.
01:12:52 Then that means at every iteration, the present distance to the global optimum is always closer
01:13:03 to the last step's distance to the global optimum, all right?
01:13:07 So in that case, we call it a linear convergence.
01:13:11 It's like the distance is linearly decreasing over the iterations, right?
01:13:15 But if beta is equal to zero and p equal to one, that means as k goes to infinity,
01:13:23 you know, this is much faster than linear.
01:13:25 So we call it a superlinear, okay?
01:13:28 And p equal to two is quadratic.
01:13:30 And then the higher the convergence, the better.
01:13:35 So basically, we want it to be convergent to the global minimum
01:13:39 and also as fast as possible, okay?
01:13:45 So let's start with a setting of the gradient-based algorithm, okay?
01:13:52 Again, it's iterative.
01:13:54 We start with x sub zero and then we generate the sequence x sub k,
01:13:58 where k goes from zero to infinity.
01:14:01 X is bold-faced to indicate that it's a column vector, okay?
01:14:06 So these algorithms are deterministic, meaning that no matter how you rerun this algorithm,
01:14:12 with this same starting point, you will always have the same sequence, okay?
01:14:19 And we only care about the local optimization in this case, right,
01:14:23 which can be useful to remove the clashes, right?
01:14:26 So in this case, let's start with the simplest algorithm.
01:14:30 I'm going to stop here and continue next time.
01:14:34 In the simplest gradient algorithm, what you are doing is that every time the next sample
01:14:41 is always the present sample plus a constant times the steepest descent, okay?
01:14:52 P sub k.
01:14:53 In other words, at current x sub k, you calculate the steepest descent,
01:14:59 which is minus g sub k, where g is a gradient.
01:15:02 Because a gradient is...