Lecture 5: Classical Formulation of Protein Structure Prediction. Optimization.
Recording. Download the text transcript.
Automatic transcript; technical terms and equations may contain recognition errors.
00:01:15 [Uncertain recognition] DNA, amino acids.
00:01:19 Okay, let's get started.
00:01:20 Howdy.
00:01:22 Let's continue week three.
00:01:25 So in the first couple of weeks, we have learned enough about the chemistry, biology, computation, data, about the molecules that carry information for us to dig from data, especially proteins.
00:01:41 Right?
00:01:42 So we have learned enough that now we can start to look at one problem, focus on one of them.
00:01:49 That is the protein structure prediction.
00:01:51 And using this one, we will start with a classical formulation and use this formulation to give you an introduction to optimization from linear programming, dynamic programming, to numerical optimization.
00:02:06 And this will be this week three and four.
00:02:11 And then we will move on to machine learning and then the new formulation of structure prediction and deep learning and so on.
00:02:22 So that's the plan.
00:02:24 And then last time, so this is where we are now.
00:02:31 Using the protein structure prediction, look at it from the classical perspective.
00:02:36 And so that's where we are.
00:02:41 And what is the protein folding problem?
00:02:46 If you understand the humor in this comic, you will understand the fun about this problem.
00:02:56 So the one is asking, what do you do?
00:02:59 So the other one is answering, I make software that predicts how proteins will fold.
00:03:04 Is that a hard problem?
00:03:07 Someone may someday find a harder one.
00:03:10 Why is it so hard?
00:03:13 Well, have you ever tried to make a folded paper crane?
00:03:18 Yeah?
00:03:19 Now imagine, figure out the folds to make an actual living crane.
00:03:28 So, what just the folds?
00:03:33 Can I make cuts?
00:03:35 Well, if you can fold a protease enzyme.
00:03:38 So what is a protease enzyme?
00:03:41 That's a protein that cuts.
00:03:43 So if you want to use the analogy of folding papers to make a crane and actually a living crane, you will need to figure out how to fold.
00:03:56 But you also need to, you know, if you want to use cuts, you need to design another protein that can cut the papers.
00:04:03 Okay?
00:04:04 So that's the humor behind it.
00:04:06 So just for you.
00:04:09 So whenever you see ASE at the end of this name, it usually means it cuts something.
00:04:16 Right?
00:04:17 So protease cut proteins into amino acids and then virus usually use those amino acids to assemble into proteins that they need for their own life cycles.
00:04:27 Right?
00:04:28 So there's DNAs that cuts DNAs.
00:04:31 Right?
00:04:32 And other kind of proteins.
00:04:35 So previously we talked about the structure data.
00:04:38 Last time we talked about the database and exactly format.
00:04:41 You will have a chance to access the data and analyzing the format by yourself in one of the homeworks.
00:04:49 And we also talked about the implication and challenges specifically.
00:04:54 It's 1D, 2D or 3D data, but how do you represent it?
00:04:58 It's actually a hard question.
00:05:00 Remember, how you represent even 3D structured data determines the input to your model, which is often a neural network.
00:05:10 Right?
00:05:11 So in other words, that determines what is the function to approximate.
00:05:16 Even though you claim that, you know, deep learning models can be universal function approximators, but we're not talking about the ideal situations.
00:05:27 We are talking about the practical situations.
00:05:29 So you have to wonder what kind of input-output relationships are easier to be captured or replicated or approximated by deep learning models.
00:05:39 And what kind of deep learning models?
00:05:42 And we didn't have time, but I hope you could read those hypothesis-driven data analytics.
00:05:49 Two case studies about what's the relevance of protein structure data and how do we use them to understand the mutations found in cancer or other kind of diseases.
00:06:02 So that was what happened the last time.
00:06:05 So now, again, as I said, we're going to start with the protein tertiary structure prediction.
00:06:11 In short, I call it a structure prediction.
00:06:13 As I said, the tertiary structure is a global structure of the protein, and you can regard it as a point cloud of all atoms.
00:06:21 But keep in mind that these atoms are bonded with each other according to a known topology.
00:06:29 You know what amino acids are there in a sequence linked in a linear order by peptide bonds.
00:06:38 And also, within each residue, you know what atoms are bonded together in what ways.
00:06:43 So those are already known, right?
00:06:45 And then there are those non-bonded interactions across atoms.
00:06:50 So, in other words, I think it's safe to say that it's also a manifold, right?
00:06:56 So we're going to start looking at this motivating application and think about, you know, when you start with applied problem, especially in our research, usually it involves three steps.
00:07:09 You first of all have to mathematically model this problem.
00:07:14 In other words, you have to translate this applied challenge into a computationally accessible and a solvable problem.
00:07:21 So that's called mathematical formulation or modeling.
00:07:24 And that is very important.
00:07:26 When you do the modeling, you have to ask, how can I do this transformation from application to mathematical models?
00:07:34 So that's the first thing you have to keep in mind.
00:07:37 Second thing is once this computational problem is formulated, right, you need to think about algorithms.
00:07:47 You have to have algorithmic thinking.
00:07:49 So how can I solve this problem with high efficiency, accuracy, and with other kind of, you know, guarantee or other kind of desired properties?
00:07:58 That's the second thing you have to think about.
00:08:00 And of course, just being able to formulate it into a mathematical problem and thinking about it, right?
00:08:06 And thinking about it from algorithms and maybe even come up with a good algorithm is not enough because you have to test it.
00:08:13 So who's going to test it for you?
00:08:15 Well, it's you yourself, right?
00:08:17 So the third aspect is computer programming, right?
00:08:20 So you have to test your algorithm, right?
00:08:23 This whole process of mathematical modeling, algorithm thinking, and computer programming forms a feedback loop, actually.
00:08:33 Because after your numerical test of the algorithms, you will find the remaining gap that can be filled better.
00:08:41 Maybe this tells you to better formulate your problem or better improve your algorithms, right?
00:08:48 So in this process, there's also additional thing because so far, you know, I'm talking about mathematical modeling, algorithm thinking, and computer programming.
00:08:58 But as we know that now, this research is getting increasingly driven by data.
00:09:05 So this whole data pipeline also has to be embedded.
00:09:09 That includes your understanding of the data, curating of the data, and split them in the ML, machine learning accessible ways,
00:09:17 and then knowing how this data can answer what kind of questions.
00:09:20 So that's also important.
00:09:22 So keep that in mind as well.
00:09:25 So I'm going to look at the computational modeling parts today to show that how this problem can be formulated in different scenarios, right?
00:09:35 And then use this to motivate the approach that is optimization approach.
00:09:40 There is also a lot of learning involved.
00:09:43 But I want to talk about machine learning after the protein structure prediction.
00:09:48 So I will move or disregard some subjects, sub topics in the structure prediction if it's heavily involved in machine learning, okay?
00:09:58 Also because it's largely revolutionized in the last four or five years, okay?
00:10:04 And for those of you who haven't taken optimization before, there is a chapter one of the book called Numerical Optimization.
00:10:16 You have the electronic copy access.
00:10:18 I probably gave the link in the syllabus.
00:10:20 So you have the access through our library, and I provided the PDF of chapter one.
00:10:25 No matter you have learned optimization before or not, this is a great survey for you to learn about the general concepts.
00:10:33 Of course, these concepts will also be covered today as well, even if you have never learned about it, okay?
00:10:39 So that's the plan for today, okay?
00:10:42 Any questions?
00:10:46 Okay, so let's get started.
00:10:48 So whenever you start talking about the protein structure prediction, you already know the definition now.
00:10:54 You start with the input of the sequence.
00:10:56 You know what the sequence format, like in FASTA format.
00:10:59 It's like a text written in the alphabet of 20 letters.
00:11:01 You also know what's the output, right?
00:11:04 Including the format, like PDB format of the output.
00:11:07 The question is, how do I solve it?
00:11:09 How come this is a computational problem, right?
00:11:12 So now, you know, imagine that you are a data scientist or machine learning scientist, right?
00:11:17 Or machine learning engineer in your company, right?
00:11:21 And I'm a customer who is trying to get some consulting help from you, right?
00:11:26 So I know about my application problem.
00:11:29 I need to solve for protein folding problem, okay?
00:11:32 I don't know how this can be computationally solved at all.
00:11:35 So I'm going to ask you, what questions are you going to ask me?
00:11:40 So that you can help me figure out a computation approach to solve the protein folding problem.
00:11:46 Pardon me?
00:11:51 The type of the input and output.
00:11:53 The type of the input and output.
00:11:55 Good, right?
00:11:56 So that you already have learned, right?
00:11:59 Good question.
00:12:00 Good one.
00:12:01 Right, thank you, Nami.
00:12:03 Other questions?
00:12:04 Does the output follow input input?
00:12:05 It has to be some sort of relationship with the input and the output for the computer to solve some sort of finance thing.
00:12:17 So you are talking about the relationship between the input and output.
00:12:21 What is the exact, can you make it more specific?
00:12:23 What questions?
00:12:24 Do you want to ask me whether that relationship is known or what?
00:12:28 So is it, what's the correlation between the input and output?
00:12:35 Good point.
00:12:36 What's the causal or correlational relationships between the input and output?
00:12:41 Is that right?
00:12:42 Yeah, thank you.
00:12:43 Good one.
00:12:44 All right, so, yeah, thank you, Nami.
00:12:47 Thank you, Amy.
00:12:48 All right.
00:12:49 Any other questions?
00:12:50 These are very, very good questions.
00:12:52 Size of the input data set.
00:12:54 Size of the input data set.
00:12:55 Very good question.
00:12:56 Yeah, very good question.
00:12:57 And so we, you know, we all know that we are better than the naive view of, you know, any input-output relationships can be captured by, you know, a universal function approximator like deep learning model.
00:13:11 So we know that we are, we are not like naive like that, right?
00:13:15 It's not like every, you know, input-output kind of prediction problem can be solved by supervised machine learning using some deep learning models.
00:13:24 So the, so the, so the, the question you are asking about the data size is also a good point, right?
00:13:29 If your data size is large enough, you probably can believe that a little bit more, right?
00:13:34 But also how large is large enough?
00:13:37 If your data size is large enough, I guess that also depends on some questions like what Nami asked, you know, the input-output kind of characteristics.
00:13:44 And then you also know that, you know, no matter you are going to rely on the deep learning or not, right?
00:13:51 You also want to ask what else can you use, you know, whether you want to use deep learning or data science as a leading role, and the, but you still need some domain knowledge to regularize or supervise or guide your data-driven models, right?
00:14:10 So that's a domain knowledge, or maybe actually in the early days, right?
00:14:14 That's a good question that Rayan you are asking, in the early days, remember I had some statistics about the growth of the sequence and structure data?
00:14:24 When this problem first appeared 50 or 40 years ago and then got solved in the first 30 years, the structure data especially wasn't big enough for us to do what we can do now, nowadays, okay?
00:14:37 So there was another kind of way to look at this problem, that's why I call it a classical formulation, okay?
00:14:44 But it's always a good point to ask what is the causal or correlational relationship between the two?
00:14:52 So that's what I call the principle, okay?
00:14:54 So in general, very naively, for any kind of mathematical modeling task, I think I'm going to ask two questions.
00:15:02 One is what's the principle?
00:15:04 The other one is what's the data, okay?
00:15:07 So I'm going to talk about both the principle and data so that you can be better motivated to see why we're, you know, formulating the protein structure prediction problem as they were, right, in the classical age, which actually is still relevant in many aspects and is quite recent still.
00:15:27 And then we're going to talk about optimization.
00:15:30 This could be an intro or this could be a review for you.
00:15:35 So let's first of all talk about the principles of protein folding.
00:15:39 How come a one-dimensional sequence got folded into a 3D structure?
00:15:43 Do you have, have you already learned about the contents already?
00:15:48 What drives a one-dimensional sequence to fold into a 3D structure?
00:15:54 Have you learned something about it in the first or second week?
00:15:58 What is that?
00:16:01 Multiple in capital bonds between minus 7%
00:16:08 Bonds and non-bonded interactions among atoms, right?
00:16:14 Right?
00:16:15 And we have learned that due to such kind of bounded and non-bonded interactions, right?
00:16:20 Some building blocks or repeating units like to be hidden from water.
00:16:28 They are hydrophobic.
00:16:29 Some like to interact with opposite charge.
00:16:32 And some are polar means that part, overall neutral, but part positive, part negative charge,
00:16:40 which can be more flexibly interacting with other residues.
00:16:43 They tend to be enriched at the surface.
00:16:46 So the driving force is a bounded and non-bonded interactions between, among the atoms.
00:16:54 But the first force, the first driving force, it's like the Big Bang of the universe.
00:17:00 The first driving force is a hydrophobic effect.
00:17:03 So some hydrophobic residues like to hide from water.
00:17:07 So they, you know, mingle with each other and then they tend to form the core of the protein.
00:17:14 So the core of the 3D structure, right, that's being formed by the hydrophobic residue.
00:17:23 Then the polar or charged residues can still exist in the core, but they must have reasons to do so.
00:17:28 In other words, these are residues that like to mingle with other charges or polar like water, right?
00:17:36 So if you want to, you know, shield them from social life with charges or waters and then just keep them in the core of the protein and don't let them out,
00:17:47 you better give them a strong reason to do that, right?
00:17:50 Right?
00:17:51 For instance, you know, maybe, you know, in the core they still find friends like polar residues or charged-charge interactions, right?
00:17:59 That's enough to not socialize with, you know, the water or other outside surface residues, right?
00:18:07 So there must be some strong reasons to bury some polar or charged residues.
00:18:12 But then they are much more enriched at the surface because at the surface they can mingle with a lot of waters which are polar.
00:18:20 They can also mingle with other protein surfaces, right, which has a lot of polar or charged residues.
00:18:27 Then there are some aromatic interactions, sorry, and other kind of interactions.
00:18:32 So all these bonded and non-bonded interactions together stabilize the protein in the 3D structure.
00:18:39 So in other words, these bonded and non-bonded interactions were driving the protein-folding problem, okay?
00:18:48 And you can say that this, as a path, is done like sequentially so that some secondary structures which are local or super-secondary structures called motifs,
00:19:00 those local structures are formed first.
00:19:03 And then the local clusters will interact with each other to stabilize a quaternal, a tertiary structure, okay?
00:19:13 So actually the principle is already known for a long time, in 1970s.
00:19:19 But the problem is that, you know, principle is good but sometimes it's not enough for you to solve the problem, okay?
00:19:26 But it helps you to solve the problem.
00:19:29 It's actually, you know, older than you and older than me that these principles were first found by Anthosyn, okay?
00:19:36 So they're saying that the three-dimensional structure of a native protein, native protein means that, you know, biologically active.
00:19:45 So it usually corresponds to the crystal structures we see, okay?
00:19:50 So the native protein in its normal physiological milieu means that the solvent, the pH, the ionic strength, presence of other components,
00:19:59 and temperature and all these environmental factors, this protein is adopting the native structure corresponding to the Gibbs free energy of the whole system being the lowest.
00:20:15 So in other words, biophysically, we know that the structure is corresponding, or native structure is corresponding to the global optimum of a function called
00:20:28 the Gibbs free energy.
00:20:31 So in other words, this can be regarded as an optimization problem, okay?
00:20:36 So that is driving the early formulations.
00:20:40 And this can also be regarded as a case of the energy minimum principle which originated from the second law of thermodynamics.
00:20:49 That's talking about the entropy of the whole system, okay?
00:20:53 So then I will introduce, so that's a problem.
00:20:58 So let's talk about the principle without going into too much details about the principle, okay?
00:21:02 Let's talk about data, okay?
00:21:04 You know a little bit about the principle, right?
00:21:06 Right now you don't know what Gibbs free energies are and how to calculate them.
00:21:10 That's fine.
00:21:11 But then let's also look at the data in the meantime, okay?
00:21:14 So what data do we have?
00:21:16 We actually have a lot of data, but we just don't know that what data can exactly solve the problem.
00:21:21 Is that right?
00:21:22 Because I'm not talking about the input-output pairs that kind of data.
00:21:26 That's apparent.
00:21:27 You're going to always use it in the setting of supervised machine learning, right?
00:21:32 But there are other kind of data which is not apparent to you at the beginning that they can be used as well.
00:21:38 Once you find such existing data and you're going to open a new horizon, and we're talking about some of those ideas after this whole classical formulation, okay?
00:21:51 So those ideas actually directly contributed to the latter revolutions and being extremely data-driven.
00:21:59 So in this data what we have back then was just a paired data, okay?
00:22:07 Input-output pair.
00:22:08 In other words, some sequences with known structures.
00:22:11 We already know that one out of 1,000 known sequences have known structures, right?
00:22:17 So that's a ratio.
00:22:19 And we are trying to figure out back then, you know, if this is the data, back then we are trying to figure out a knowledge.
00:22:25 That is a relationship.
00:22:27 Remember back then the knowledge was not dug by, you know, deep learning.
00:22:34 So how you define knowledge is also a question, right?
00:22:37 So back then people look at the pattern or use some shallow machine learning models.
00:22:42 And then we'll talk about some of those as well.
00:22:44 But why was this knowledge useful?
00:22:47 It actually helps us do the mathematical formulation or modeling.
00:22:51 You will see that.
00:22:52 So first of all I want to introduce a couple of concepts, right?
00:22:58 So one is similarity in the input domain, the sequence, okay?
00:23:03 So you can use sequence identity which is a percentage of the matched or identical nucleic acids or residues, depending on whether it's DNA or protein, in the aligned sequences.
00:23:15 Okay?
00:23:16 You haven't learned how to align two texts yet.
00:23:19 No problem.
00:23:20 We'll talk about it in the next lecture.
00:23:22 Okay?
00:23:23 But just right now keep in mind that we can somehow align two sequences written in the same language or alphabet.
00:23:30 And then we can calculate what's the percentage of the matched repeating units.
00:23:36 And that's called the sequence identity.
00:23:39 When calculating sequence identity, you are looking at each aligned pair and asking whether it's zero or one, right?
00:23:48 But you could imagine that some residues are not exactly the same like each other, but they are similar, right?
00:23:56 For instance, arginine and lysine.
00:23:58 There are two letters, right?
00:24:00 But are you going to give you the zero?
00:24:02 Well, remember that they are both positively charged residues.
00:24:07 So the similarity between arginine and lysine versus arginine and a hydrophobic residue like alanine shouldn't be the same, right?
00:24:16 So that's why people started to introduce some like non-binary measure for each pair of residues.
00:24:23 Then they can define the sequence similarity somehow, okay?
00:24:28 And you can use other kind of similarity scores as well.
00:24:31 We're going to explore some of them in the homework, okay?
00:24:35 And the alignment.
00:24:37 So, and then you want to ask, you know, why do I care about the similarity?
00:24:43 Remember we said that, you know, there are 1,000 times more sequences than the structures that have been seen.
00:24:50 But out of those structures, actually only one out of a hundred or one out of 1,000 folds are existing.
00:24:59 In other words, so many structures actually corresponds to a saturating and small number of folds or pattern.
00:25:06 Back then we asked why that was the case.
00:25:09 And we talked about evolution, divergent and convergent evolution driving the forces.
00:25:15 And maybe you want to reuse some folds or maybe you want to have some convergent use of different folds.
00:25:24 But looking at the evolution, the reason that we see different proteins, right, in different species sharing similarity, right?
00:25:34 This is originating from different reasons.
00:25:39 So, overall we call such phenomena the similarity between the different sequences.
00:25:48 We call them homology, okay?
00:25:50 So this homology is usually, you know, due to the descent from the common ancestor.
00:25:57 But there could be convergent evolution as well.
00:26:00 There are two kinds of homology or similar sequences, okay?
00:26:05 One is called orthologs and one is called paralogs.
00:26:08 I want you to think about it as like one is vertical and one is horizontal.
00:26:13 Okay, by vertical I'm talking about the time axis or the evolution time.
00:26:20 So, the orthologs are homologs or similar sequences originating from speciation.
00:26:29 So, one species diverged into separate species.
00:26:33 So, that's why I said it's vertical in that sense, okay?
00:26:38 So, you could have hemoglobin in mice versus in human, right?
00:26:43 They're different, right?
00:26:44 They probably had a common ancestor but they diverged since then.
00:26:50 In this case, the orthologs usually have similar functions, right?
00:26:54 The same, you know, oxygen carrying function for mice hemoglobin versus human hemoglobin.
00:27:03 But there are also paralogs.
00:27:06 So, this is due to the gene duplication, okay?
00:27:09 This is not due to the speciation.
00:27:11 This is due to the gene duplication.
00:27:14 And in those cases, they don't necessarily have very similar functions, okay?
00:27:19 So, this is the similar sequences or, you know, why we observe a lot of similar inputs, okay?
00:27:27 Now, we want to ask what are the similarities in the output, okay?
00:27:32 The structure.
00:27:33 So, one kind of measurement is sort of, you know, you need to align now not two, you're not aligning two sequences in 1D anymore.
00:27:45 You're aligning two structures in 3D.
00:27:48 So, now imagine that you have A and B, each consist of four atoms.
00:27:52 And they are trying to align them optimally so that the pairwise distances squared together and summed together is the smallest.
00:28:02 So, that's called the root mean squared deviation.
00:28:05 So, let's say after the alignment, you know that A1 is aligned to B1, A2 is aligned to B2.
00:28:12 Then you know that the corresponding distances, and then you do the squared sum of the distances, and then, you know, take the root.
00:28:21 I take the mean and then take the root.
00:28:24 That's the root mean squared distance, okay?
00:28:28 Or deviation.
00:28:29 Okay?
00:28:30 Here, you don't seem like this A and B are aligned.
00:28:33 That's because I wanted to keep them a little bit separate so that I can show D1, D2, D3, D4, okay?
00:28:40 So, you have the sum of the squared Di's, then take the average, and then take the square root.
00:28:45 So, root mean squared deviation.
00:28:51 Root mean squared deviation, okay?
00:28:55 So, in the sequence similarity, the identity is higher, the more similar.
00:29:00 In the structure similarity, this similarity actually, RMSD, is the lower, the more similar, okay?
00:29:06 Because that's the deviation.
00:29:09 So, now, let's look at the pattern in the data and see what can we get.
00:29:15 So, here you have pairs of sequences or structures or pairs of proteins, and you look at their sequence similarity or identity versus the structure dissimilarity.
00:29:29 Okay?
00:29:30 So, the x-axis, notice that I rearranged the order.
00:29:35 So, on the left, you have 100% similar.
00:29:38 On the right, you have 0%.
00:29:40 So, the sequence similarity from left to right is decreasing.
00:29:44 The structure similarity from the bottom to top is also decreasing because RMSD is the lower the less, okay?
00:29:52 So, you can disregard the different colors for the moment and focus on the different colors.
00:29:59 So, the blue crosses, which are protein pairs, okay?
00:30:03 For any random protein pairs, we can calculate the sequence or the input similarity versus the structure, the output similarity.
00:30:14 So, what did you observe?
00:30:16 You observe this trend that overall, if you are at the early stage where the sequence identity is high, right?
00:30:26 Then you see that the y-coordinate or the RMSD or the structure deviation are very low.
00:30:34 You could have outliers here, but most of them are very low, below 2-anstrom or 3-anstrom, which can be regarded as very similar structures.
00:30:44 Okay?
00:30:45 But this kind of narrow band is completely changed when your sequence identity is below 20 or 25%.
00:30:57 You still have the frontier that's going along this direction, showing that, you know, less similar sequences result in less similar structures.
00:31:08 But once the sequence identity is below some percentage, like 25 or 20, this is the much more difficult scenario, because you could have protein pairs whose sequence identity is 20% or lower, but the structure similarity is still high.
00:31:30 But you could also have some protein pairs whose sequence identity is low, but you could also have some protein pairs whose sequence identity is low and the structure identity is also low.
00:31:40 So, in other words, you sort of have the easy cases here, because you have a very narrow band distribution showing that you have very similar sequences, you have very similar structures, and the difficult cases are here.
00:31:55 Okay?
00:31:56 Does that make sense?
00:31:59 Okay, so if you look at the frontier, this tells you that, you know, this gives you the most optimistic view, right?
00:32:05 So that's the best case scenario, because that lowers the structure deviation, right?
00:32:11 But remember that this most optimistic view would be way and way off from the majority when the sequence identity is low.
00:32:20 Okay?
00:32:21 So if you see this kind of pattern, what can you do?
00:32:25 Well, then you know that when you can rely more on data, when you can rely more on principle.
00:32:30 So that's my argument.
00:32:31 And if I want to summarize, do I see any rule by eyes?
00:32:37 There's a golden rule that there is no golden rule.
00:32:40 Okay, that's a golden rule.
00:32:42 But we can still see that, as I said, the similar sequences imply similar structures, especially when the sequence identity is at least low.
00:32:49 The sequence identity is at least 30%.
00:32:51 You see that very narrow bend, so the optimistic view is not far away from the average view.
00:32:58 Then we also learned something that the structure is more conserved than sequence, because, you know, you see that very dissimilar sequences from 100% identical all the way to 20%, right?
00:33:11 Or even lower, could have very similar structures, right?
00:33:16 And, you know, this explains what I said last time that knowing that only 1,000, one of the other 1,000 sequences have structures, is not necessarily saying that structure data is that limited.
00:33:33 You also have to factor in the consideration that structure is much more conserved.
00:33:38 So the data is more limited, but it doesn't mean that the coverage, the data coverage in the structure space is 1,000 times sparser than the sequence space.
00:33:48 Do you get what I mean?
00:33:50 Right?
00:33:51 Because very dissimilar sequences could have very similar structures, okay?
00:33:58 So it doesn't mean that the structures are that limited to enable a data-driven approach, okay?
00:34:05 So especially in the recent years, we have 180K now.
00:34:09 So that directly contributed to the land-shifting technology.
00:34:14 So, then that means we can divide and conquer, because, you know, when you first touch a problem, the biggest mistake you want to avoid is to solve it in the general case.
00:34:28 You know, if it's the first time you work on this problem, you don't want to solve the most generic form, right?
00:34:34 I want to optimize a function f of x without any assumption, bad idea.
00:34:40 I want to solve the protein structure prediction problem for any kind of sequences, bad idea.
00:34:47 You've got to make it more specific.
00:34:49 You've got to make it milestone, okay?
00:34:52 So if this is the first subject that, you know, you are the one of the pioneers looking into this problem, using protein structure prediction as an example,
00:35:00 you want to start with the low-hang fruit.
00:35:03 Where is your low-hang fruit?
00:35:05 Here.
00:35:07 Just one point.
00:35:08 When you know that you already have sequences who are very similar and who have structures already solved, then I know that my answer is very similar.
00:35:17 Right?
00:35:18 The query sequence must have very similar structure compared to the template sequence, okay?
00:35:23 Then the rest is how to find the template, okay?
00:35:26 So let me call this region when the sequence identity is above 30%.
00:35:33 Let me call it a safe zone, right?
00:35:36 In this safe zone, the lowest kind of fruit is, you know, you can find these identities above 30%, and the structures are very likely similar.
00:35:47 So in other words, you can borrow the structure of a template, if you know which one is a template, and then you can modify the template structures as needed.
00:35:58 This is also called homology modeling.
00:36:01 In other words, you have a homology there, and you know you can find it.
00:36:06 Okay, right, you don't have the structure of the query protein, but you have the sequence, and you know that this sequence is similar enough to a template sequence that you can draw the conclusion that their structures must be similar.
00:36:18 So this is a safe zone.
00:36:20 Okay, so I can give you the glimpse of the homology modeling.
00:36:23 So imagine that you have a query sequence, and you have a bunch of template sequences.
00:36:30 The difference between the query and the template sequence lies in that the query sequence doesn't have the structure, and the structure needs to be predicted.
00:36:40 And the template sequences, for instance, in the bottom, their structures, sorry, actually in this case, the top row is a template, and the bottom row is the query.
00:36:52 Okay, so the template sequences already have the structures available, like in this one.
00:36:57 Okay, so if you can identify the template 1shg, the four-letter PDB code, for the query sequence, and you also figure out how they are aligned.
00:37:09 So you see these dashes are gaps, so you see these dashes are gaps.
00:37:12 We're going to talk about sequence alignment next time.
00:37:16 If you can figure those out, then you can, you know, you can look at the common part and, you know, use directly the common part's backbone structure.
00:37:26 So let's say these segments are the aligned common regions.
00:37:32 Okay, and then for the part that are different, I can somehow insert them.
00:37:37 Okay, I can somehow insert the loops and add the side chains, right?
00:37:42 But I can borrow the backbone of the aligned portion from the template.
00:37:47 So that's the whole idea.
00:37:49 And there are a lot of tools for you to do that.
00:37:51 I don't want to talk more about the details.
00:37:56 But there are still remaining problems, right?
00:37:59 So if I already found a template for the given pair of query and template,
00:38:04 how do I know which part of the template backbone structure to borrow?
00:38:09 In other words, how do I align them?
00:38:11 That we still don't know, right?
00:38:13 How do I align them optimally?
00:38:16 And then this is about a given pair, you know, of query and template.
00:38:22 But remember, there are many templates, many templates,
00:38:27 180,000 protein sequences with structures solved in different conditions.
00:38:32 How do you find the best template or templates quickly?
00:38:38 That's another question, right?
00:38:40 So both can be formulated as optimization problems.
00:38:43 And I want to talk mostly about the first problem of sequence alignment in the next lecture.
00:38:49 Okay?
00:38:49 And the second question is actually about the database search,
00:38:54 which is a classical question for, you know, a lot of CS algorithms are good at this.
00:39:03 Because why?
00:39:04 Because the sequences are like strings.
00:39:07 There are a lot of string algorithms already existing.
00:39:09 So that is less difficult.
00:39:13 But this is why the early stage of protein structure prediction or the lower hanging fruits are in the safe zone.
00:39:22 And then that's how they're formulated.
00:39:25 Okay?
00:39:26 Any questions?
00:39:27 Any questions?
00:39:28 Any questions?
00:39:29 Okay.
00:39:30 Seeing that these problems can be formulated as optimization,
00:39:34 I think it's important to now see the big picture.
00:39:41 I'm going to talk about the classical structure prediction.
00:39:44 Okay?
00:39:45 The rationales, the problems, and the approaches.
00:39:47 So the central question is how much can one leverage the homology data?
00:39:55 So in the safe zone, we know that we can find some templates whose sequence identity is above 30%.
00:40:01 So the rationale is that they are similar enough to result in similar structures.
00:40:08 Okay?
00:40:09 So that's the rationale.
00:40:12 And given the rationale, we can do the homology modeling.
00:40:14 So we first figure out which template, right, from the database search, which is usually a string algorithm.
00:40:22 Then for the given pair, we can do the sequence alignment, use kind of dynamic programming or some faster versions, but approximate versions.
00:40:31 Right?
00:40:31 Recently, people are even using neural networks to do the alignment between sequences.
00:40:36 That's also possible.
00:40:37 So, and then if you go to the other extreme, I call it a midnight zone because it's very dark, the sequence identity is less than 20%.
00:40:49 In other words, you are in that broad range here.
00:40:55 You know, you have all these sequences whose similarity is below 20%.
00:41:00 Some of them have very similar structures, but some of them have very different structures.
00:41:06 And you have no idea which ones can be good templates, right?
00:41:11 Because the only information you have is in the sequence.
00:41:14 In the sequence space, they are just below 20%.
00:41:16 So, in other words, in the midnight zone, when the sequence identity is not enough to sustain the relationship between similar sequences and similar structures,
00:41:29 when the sequence similarity is not enough to sustain similar structures, then you have to rely on the principle a little bit more.
00:41:38 So, we have to follow the energy minimum principle that you have learned.
00:41:42 And that would involve a lot of energy minimization, especially the numerical optimization.
00:41:49 But there is not a clear cut between the data-driven and the principle-driven approaches because, as I said,
00:42:00 you haven't learned what is Gibbs free energy so far.
00:42:04 But you will learn that, you know, there's very difficult and challenging to calculate them exactly.
00:42:10 It's not like I tell you a function, like a quadratic function or, you know, cubicle function that you can optimize them.
00:42:16 In those cases, you probably have to first approximate them with some physics.
00:42:22 Or later on, actually, they are gradually replaced by shallow machine learning models, right?
00:42:28 And then, nowadays, replaced by the deep learning models, okay?
00:42:33 And then, in between, there are some twilight zones.
00:42:38 This time, I don't want to talk too much about the twilight zones because I think the twilight zone is now a little bit eating away due to the new technologies.
00:42:49 In other words, this is a classical view, okay?
00:42:53 The classical, excuse me, the classical view had to rely on some easy-to-dig signal that is a sequence identity, local or global.
00:43:05 But now, remember, deep learning is able to cover some patterns that is not immediately clear to our human brains or eyes.
00:43:13 You see what I mean?
00:43:14 So, in other words, the difficulty, right?
00:43:18 The difficulty may not be exactly now broken down in this way anymore.
00:43:25 I'm not talking about a thresholding of 20 or 40 percent.
00:43:29 I'm talking about the measure of sequence identity itself, even, okay?
00:43:34 In other words, protein sequences or structures can be similar in different ways that are not immediately clear to our eyes.
00:43:44 But in the twilight zone, the rationale was that we don't have similar enough sequences, but we can make it more vague.
00:43:55 Instead of using similar sequences, we can say that the proteins have similar profiles, right?
00:44:02 And if they have similar profiles, they have something.
00:44:06 The labels are also similar, but not that similar.
00:44:09 So, they don't have similar structures, but they have similar folds, remember?
00:44:13 There are only thousands of folds for all kinds of structures we have.
00:44:18 So, in that case, the question is really about, you know, how do you identify the fold or the folder template?
00:44:26 Then, how do you borrow the different parts of the structures?
00:44:33 So, that's going to be talked about last or skimmed, okay?
00:44:36 Okay, now, let's keep that in mind and start with the safe zone, the lowest hanging fruit.
00:44:43 Again, you don't want to solve the most...
00:44:45 How do you feel so much?
00:44:46 I think I'm less than better than I can.
00:44:48 Yes.
00:44:49 So, again, we don't want to solve an overly generic problem right away, and we want to start with the whole low-hanging fruit.
00:45:08 Okay?
00:45:10 So, our first milestone is a safe zone.
00:45:12 We figured out what is the rationale and, correspondingly, what is the approach?
00:45:17 Okay?
00:45:17 So, let's talk about optimization, and let's get prepared, because a lot of optimization are being involved.
00:45:26 So, many of you have already taken optimization, but whether you have taken it or not, I hope the introduction gives you a good overview again, or a review.
00:45:39 Many problems can be formulated as and solved by mathematical optimization, including machine learning or deep learning, okay?
00:45:48 One of the...some of the machine learning models directly got a better understanding and solution, thanks to optimization, such as support vector machine.
00:45:58 Many deep learning problems actually can be formulated into a mathematical optimization and then solved by some numerical optimization algorithms, okay?
00:46:11 So, that's why we want to talk about the general form and the branches of the optimization problem, okay?
00:46:17 In general, you can think of it as minimizing f sub 0 of x.
00:46:24 So, this f sub 0 can be a single dimension, scalar, or multiple objective functions somehow, okay?
00:46:32 And you may want to combine the multiple objective functions in the weighted sum or any kind of ways.
00:46:36 But let's simplify it and regard it as a single objective function for the moment.
00:46:45 And then there's a function of x.
00:46:47 This x does not have to be a scalar, it can be a vector, so it could be bold-faced and regarded as a vector.
00:46:54 Whenever it's a vector, let's by default assume that it's a column vector, okay?
00:47:00 So that we can write into the linear algebra form later on.
00:47:04 Then you have the constraints.
00:47:06 So, you are minimizing f 0 of x, subject to m constraints, where these constraints are written as f sub i of x, less than or equal to b sub i.
00:47:19 So, this is actually a very generic form of the constraints.
00:47:24 You may wonder, well, what if I have equality?
00:47:27 Well, you can use two inequalities and the intersection of them becomes equality, right?
00:47:33 So, this is a very generic form.
00:47:35 I didn't talk about what's a form of f 0 or fi that can be split and talked about later on.
00:47:42 So, in other words, there are three key ingredients in optimization.
00:47:48 One is the decision variable x that you want to minimize, okay?
00:47:53 So, I should say minimize, you know, you try to find the best x, okay?
00:47:57 You are minimizing over x.
00:47:59 You are minimizing f 0 of x over x.
00:48:02 So, x is the decision variable or variables.
00:48:06 And then, what we are minimizing is objective function or also called the cost function, okay?
00:48:14 And lastly, we have bunch of constraints which defines the feasible space for all feasible solutions, for all the decision variables that satisfy the constraints.
00:48:28 So, that's called the feasible solutions and the feasible solutions reside in the feasible space.
00:48:34 The feasible space is defined by the intersection of all these constraints, okay?
00:48:39 So, now let's talk about the different types of optimization problems based on these three ingredients, okay?
00:48:50 Let's start with the decision variable, okay?
00:48:53 So, depending on whether x is continuous or discrete or mixed, you could have different kind of optimization problem, right?
00:49:03 So, in the case of continuous x, then you can, you know, use the derivatives or finite differences easily, right?
00:49:12 But imagine that if x is a hyperparameter in your machine learning model, like the depths of your GCN, graph convolution and neural networks,
00:49:25 or the number of neurons in that layer, it's not a continuous number, it's discrete, right?
00:49:34 So, in that case, you may end up, you know, solving a different kind of problem.
00:49:39 This could be integer programming, if the feasible set or the feasible solutions of the decision variables are integers,
00:49:48 or this could be just combinatorial.
00:49:50 So, for instance, I want to solve the optimum knapsack problem, you know, I want to pack enough things into my knapsack,
00:50:00 which has a fixed volume, right?
00:50:03 But the different items have different volumes and different values, right?
00:50:08 I want to pack as much value as possible into that fixed volume of knapsack, right?
00:50:14 So, that's the combinatorial optimization problem.
00:50:17 Then you can have some mixed integer programming or mixed problems, especially when you are doing the hyperparameter optimization, right?
00:50:26 You could have discrete hyperparameters, as I said, but you also have continuous hyperparameters like learning rate, right?
00:50:33 So, that's the decision variable.
00:50:36 Now let's look at the objective function or the cost function.
00:50:40 So, this is very important because in the past people can ask how easy is it to solve the optimization problem,
00:50:51 and they need to look at the decision variable, the constraints, but also heavily look at the objective function.
00:50:57 There's a key concept about whether a function is convex in x or not, not convex, okay?
00:51:07 And actually, that is the separation between easy and hard problems, okay?
00:51:18 So, what does convex objective function mean?
00:51:23 What does convex objective function mean?
00:51:26 Let me see whether I have an illustration.
00:51:28 If not, let me try to write it here.
00:51:31 So, anyone want to tell me?
00:51:39 I think many of you have already learned.
00:51:41 What is a convex function in x?
00:51:44 Well, let's draw.
00:51:50 Let's see what happened.
00:51:54 What happened?
00:52:03 Pen does not work, huh?
00:52:24 Pen does not work.
00:52:26 Okay, let me use the whiteboard then.
00:52:31 Is there a pen for the whiteboard?
00:52:33 [Uncertain recognition] Masakan .
00:52:41 [Uncertain recognition] Step 5 times per shoulder .
00:52:45 Thank you.
00:53:15 Any answers?
00:53:30 What is the…
00:53:41 You are talking about a conclusion for convex functions or convex optimization.
00:53:51 You are now talking about what is a convex function.
00:53:58 Let's start with the function.
00:54:10 What is a convex function?
00:54:17 So I think that's a very accurate mathematical definition.
00:54:36 Can you use a plain language?
00:54:43 That's wonderful.
00:54:46 Right.
00:54:47 Higher than the actual function.
00:54:54 So let's look at three functions.
00:54:56 Right.
00:54:57 So which function is convex?
00:54:59 And let's say this is x and this is y.
00:55:04 Or f of x.
00:55:07 Okay, which function is convex?
00:55:09 The first one is convex.
00:55:11 Why?
00:55:12 As Nami said, if you pick any arbitrary two points in the feasible set of x and then you draw a line.
00:55:28 And if the line is always above the function segment, then that's called convex.
00:55:39 Mathematically, what it means is that this is x1, this is x2, and we have f of x1, and this is f of x2.
00:55:54 Right.
00:55:55 The height.
00:55:56 And then if you have something in the middle, which is a convex combination of x1 and x2.
00:56:03 So this point is like a weighted average.
00:56:09 That is lambda x1 plus 1 minus lambda x2, where lambda is between 1 and 0.
00:56:22 So in other words, this is called convex combination.
00:56:25 Okay.
00:56:27 X1 and x2.
00:56:38 So then this height is f of lambda x1 plus 1 minus lambda x2.
00:56:49 Right.
00:56:50 Remember, this lambda can be any value between 0 and 1.
00:56:54 So when you are changing lambda, this point is essentially hovering over the whole line segment.
00:57:00 Is that right?
00:57:01 So what we need to make sure is that this point is always above or equal to the function.
00:57:14 So what is this point?
00:57:15 Sorry.
00:57:16 Sorry about that.
00:57:17 I made a mistake.
00:57:19 You didn't correct me.
00:57:25 So this height is the convex combination of the two function values.
00:57:39 Right.
00:57:40 Right.
00:57:41 Right.
00:57:42 Nami, you probably figured it out.
00:57:47 And what I wrote before was actually this point.
00:57:52 It's a function value at the convex combination of the two points.
00:58:01 So this relationship is hold.
00:58:10 Right.
00:58:11 So that is the definition that the function is convex.
00:58:18 Okay.
00:58:19 So if for any, so in other words, if I try to summarize, right, for any x1, x2 that belongs
00:58:31 to the feasible set, let me use a capital X. And we have f of lambda x1 plus 1 minus lambda
00:58:40 x2 less than or equal to lambda fx1 plus 1 minus lambda fx2, where lambda is between 0 and 1.
00:58:56 So this is the definition of a convex function.
00:58:59 Okay.
00:59:00 So why do we care about the convex function?
00:59:04 If the function, objective function is convex and the feasible space defined by the constraints
00:59:12 is also convex.
00:59:14 Okay.
00:59:15 Then it's a convex optimization problem.
00:59:19 Okay.
00:59:20 So this is a convex function.
00:59:22 Right.
00:59:23 So what about the convex space?
00:59:30 What kind of feasible space is convex?
00:59:39 Any intuitive explanation?
00:59:42 Is this convex?
00:59:46 Is this convex?
00:59:47 Is this convex?
00:59:48 Is this convex?
00:59:49 Let me remove the first one.
00:59:53 Circle.
00:59:54 And then make this one a little bit more.
00:59:55 Is this convex?
00:59:56 Is this convex?
00:59:57 Is this convex?
00:59:58 Let me remove the first one.
01:00:01 Circle.
01:00:02 And then make this one a little bit more.
01:00:20 So which one is convex?
01:00:21 Two.
01:00:22 Two.
01:00:23 Two is convex?
01:00:24 Okay.
01:00:25 Anything else?
01:00:26 One is also convex.
01:00:27 It's a sphere.
01:00:28 But why is the three not convex?
01:00:29 The weighted sum of some points is not in the space.
01:00:34 Good point.
01:00:35 So we can see that.
01:00:36 So we can see that.
01:00:37 So we can see that.
01:00:38 The weighted sum of some points is not in the space.
01:00:39 So we can see that.
01:00:40 So we can see that.
01:00:41 So we can see that.
01:00:42 The weighted sum of some points is not in the space.
01:00:56 Good point.
01:00:57 So we again look at any arbitrary two points within the feasible set and draw a line like
01:01:04 before.
01:01:05 And we ask ourselves, is this line still contained in the feasible space or not?
01:01:11 Let's call this feasible space x.
01:01:14 Okay?
01:01:15 And again, you have x1 and x2 which belong to the feasible space.
01:01:22 Okay?
01:01:23 Arbitrary.
01:01:24 Okay?
01:01:25 This means for any x1 and x2 belong.
01:01:27 Okay?
01:01:28 If you draw that line, the blue line basically says what?
01:01:32 So we have lambda x1 plus 1 minus lambda x2 where lambda is between 0 and 1, right?
01:01:40 So this is convex combination.
01:01:42 If lambda is outside of 0 and 1 range, then it could go beyond this line, right?
01:01:47 So this one still belongs to x, then it's convex, right?
01:01:52 Because the segment is entirely in the feasible space, right?
01:01:56 But in other cases, if I pick this one, right?
01:02:01 So as long as there's one violation is not convex.
01:02:05 Remember, this is regarded as for all.
01:02:09 Okay?
01:02:10 So if your objective function is convex and your feasible space is convex, then the problem,
01:02:20 optimization problem, is convex.
01:02:22 Optimization, then it's easy.
01:02:24 Okay?
01:02:25 For instance, in this case, let's say you have a two-dimensional space and you have the discrete
01:02:34 grids.
01:02:35 Is this convex or not?
01:02:37 This is a discrete optimization.
01:02:40 So the feasible space are those points.
01:02:42 Is this convex?
01:02:47 Just draw a line.
01:02:49 The line is not in the feasible space, right?
01:02:52 So in other words, discrete optimization very often is not convex and can be difficult.
01:03:01 Okay?
01:03:02 So in the early days, people asked whether the objective function f0 and the constraints are
01:03:11 linear.
01:03:12 And that's called linear optimization and that's usually regarded easy.
01:03:16 Okay?
01:03:17 But then people learned that actually, you don't have to just look at linear.
01:03:22 So as long as the function and the feasible space is convex, right, then it's easy to solve.
01:03:29 Okay?
01:03:30 There are different techniques, including interior point methods to solve this convex optimization.
01:03:39 Okay?
01:03:41 And, but besides the fact that what is the separation between convex and non-convex, we know that one
01:03:48 is, you know, easy and one is difficult, right?
01:03:53 In the convex case, sometimes you have the closed-form solution, for instance, polynomials, right?
01:04:00 But sometimes you don't have the closed-form, okay?
01:04:06 One of the challenge, you know, when you don't have the closed-form, you think that, okay, maybe I can use numerical optimization using gradients if it's continuous.
01:04:15 But remember, there's one key difference between the global, between the low convex and non-convex function, right?
01:04:22 So let's first forget about the feasible space being convex or not and just look at the function.
01:04:29 You see that in the case of non-convex optimization, right, you have a global optimum, right?
01:04:39 That's the lowest across the whole landscape.
01:04:44 But you also have local optimum.
01:04:48 That is the lowest only in its local region.
01:04:52 So a lot of algorithms are good at finding the local minimum, but in general, finding the global optimum for a non-convex optimization problem is not a solved problem, okay?
01:05:07 So now let's talk about the easiest case.
01:05:12 That's called the linear programming, okay?
01:05:14 So the easiest case is linear programming.
01:05:17 So let's review it.
01:05:18 Let's see whether, you know, what is the decision variable?
01:05:23 It's continuous, and the objective function and the constraints are both linear.
01:05:28 So now let's try to look at this case.
01:05:31 Again, both objective function and constraints are linear in X, right?
01:05:36 And the X is continuous.
01:05:38 So it's the easiest among the easiest, okay?
01:05:41 So let's try to interpret it, okay?
01:05:45 And look at the feasible space.
01:05:48 Let's use a two-dimensional, okay?
01:05:51 So what is the constraints, right?
01:05:54 So again, your F, so linear programming.
01:05:58 F0 of X, remember X is a vector, right?
01:06:03 So it's, okay, C is a vector, a column vector.
01:06:12 I take the transpose, then it's in the product.
01:06:14 So it's linear, okay?
01:06:17 And F i of X, right, is equal to A i.
01:06:24 And this is less than B i, okay?
01:06:42 So that is, again, linear, okay?
01:06:47 So now let's look at the geometric interpretation of this linear programming problem.
01:06:54 So what's the feasible space like?
01:06:57 So our question first is, what's the feasible space like?
01:07:01 All right, because right now you're not fully convinced that it's a convex optimization, okay?
01:07:07 So the linear function is both convex and concave, so that's not a problem, okay?
01:07:14 So now let's look at the feasible space.
01:07:16 Let's, for the simplicity, regard X in the two-dimensional space, okay?
01:07:22 So let's look at this form, this function form.
01:07:26 Let's say X in the two-dimensional space.
01:07:30 So what's the feasible space like?
01:07:35 So in the third-dimensional space, you have an intersection of M inequalities, right?
01:07:44 So what does each inequality define?
01:07:48 It's a half space.
01:07:58 So in general, X is n-dimensional space.
01:08:01 And A i transpose times X equal to B i defines a hyperplane in that space, okay?
01:08:10 So let's say if it's a two-dimensional space, right?
01:08:14 Then A i transpose times X equal to B i is simply a line, right?
01:08:21 So let's say A i is going this direction, right?
01:08:23 So if it's less than or equal to, depending on where A i is, so let's say A i is going this direction, right?
01:08:36 So if it's less than or equal to, it means what?
01:08:52 The feasible space is, right?
01:08:58 So that's what's called half space.
01:09:04 And this is a plane, a hyperplane.
01:09:09 Because plane is two-dimensional, but you could have M minus one dimensional, okay?
01:09:14 Let's say x belong to n dimension.
01:09:22 Okay?
01:09:24 Okay, so then this is a n minus one dimension, right?
01:09:33 Okay, so in the two-dimensional space, it's just a line, okay?
01:09:37 So each inequality, linear inequality, defines a half space.
01:09:43 Now you have n of them.
01:09:44 You have to take the intersection.
01:09:46 What do you get at the end?
01:09:50 You may have another, right?
01:09:53 Let's say this is a1.
01:09:55 This is a, you know, a i, that's fine.
01:09:58 And then you have a j less than or equal to bj.
01:10:05 So in this case, for instance, a is going this direction.
01:10:11 Then less than or equal to says it's like this, right?
01:10:16 Then you have another.
01:10:17 Then you have another.
01:10:18 You have another.
01:10:20 And then if you look at the intersection, right,
01:10:24 you may just have the intersection.
01:10:28 So the intersection of the hyperplane,
01:10:31 because all the constraints,
01:10:37 M
01:10:37 hyperspace,
01:10:41 which is n minus 1d.
01:10:45 You have M half space,
01:10:49 sorry,
01:10:49 n d,
01:10:50 half space is n d.
01:10:52 Hyperplane is n minus 1d.
01:10:56 So you have all these M half spaces intersecting with each other.
01:11:00 And what do you get in the end?
01:11:04 What's the intersection of M half spaces?
01:11:07 What do you get here?
01:11:18 This is a polyhedron, right?
01:11:21 Right?
01:11:22 So this is a polyhedron.
01:11:23 Okay.
01:11:24 Now I have talked about a feasible space.
01:11:26 Now let's talk about the objective function.
01:11:29 Okay.
01:11:30 So the objective function,
01:11:32 now that you are familiar with my geometric illustration,
01:11:39 you might be okay to understand the concept.
01:11:46 Again, let me move the feasible space here.
01:11:50 Right?
01:11:51 So let's say this is the feasible space.
01:11:55 Right?
01:11:55 This is our x.
01:11:58 Okay?
01:11:59 So x belongs to the feasible space x.
01:12:02 Okay?
01:12:03 Which is a polyhedron.
01:12:06 Okay?
01:12:07 So now what's the objective function?
01:12:09 So with the illustration,
01:12:11 now you can understand that,
01:12:13 oh,
01:12:14 the objective function in this illustration is what?
01:12:17 Is linear.
01:12:18 Right?
01:12:19 So it's like what?
01:12:22 So depending on what's C,
01:12:24 so it's like,
01:12:25 this polyhedron is defined by the constraints,
01:12:29 vectors like A.
01:12:30 Right?
01:12:30 But the objective function is what?
01:12:33 For instance,
01:12:34 like this.
01:12:36 This is,
01:12:37 for instance,
01:12:39 C transposed times x
01:12:42 equals to something.
01:12:45 Okay?
01:12:45 Equals to some constant.
01:12:47 Right?
01:12:48 And the C vector,
01:12:49 for instance,
01:12:50 is going this direction.
01:12:51 Right?
01:12:51 So if I swipe
01:12:53 this linear,
01:12:57 you know,
01:12:57 this line in the two-dimensional space
01:13:01 or this hyperplane
01:13:02 in the n-dimensional space,
01:13:04 if I swipe it along this vertical direction,
01:13:08 this objective function's value
01:13:10 is getting smaller or bigger.
01:13:11 If I go the direction of C,
01:13:16 like go this direction,
01:13:19 right?
01:13:19 Let's say I go this,
01:13:21 here.
01:13:23 Is the function value getting smaller or bigger?
01:13:32 Along the direction of C?
01:13:33 It's getting bigger.
01:13:37 Right?
01:13:37 So in other words,
01:13:39 if you move this function,
01:13:44 this hyperplane,
01:13:46 along the direction of the C vector,
01:13:49 and the function value is getting,
01:13:52 you know,
01:13:53 hotter.
01:13:55 Right?
01:13:55 And then if you move it
01:13:59 opposite to this direction,
01:14:01 the function value
01:14:03 is getting smaller.
01:14:05 Right?
01:14:07 Right?
01:14:07 So if you want to optimize
01:14:10 this C transpose times X,
01:14:13 if there's no constraint,
01:14:15 you better go all the way
01:14:17 to the infinity.
01:14:20 Right?
01:14:20 That means
01:14:21 this optimization problem
01:14:23 is unbounded from below.
01:14:26 Because the feasible space
01:14:27 is everything,
01:14:28 so I can move this line
01:14:29 all the way to
01:14:30 that direction
01:14:31 goes to infinity.
01:14:32 That's unbounded,
01:14:34 right?
01:14:34 But unfortunately,
01:14:36 it is not.
01:14:37 I have the feasible space,
01:14:38 so now you tell me
01:14:39 where is
01:14:40 the global minimum.
01:14:43 Where is the optimum
01:14:45 in this constrained
01:14:48 optimization problem?
01:14:52 Yes.
01:14:53 It's when this plane
01:14:55 [Uncertain recognition] last leave
01:14:59 [Uncertain recognition] the height,
01:15:02 [Uncertain recognition] the...
01:15:03 [Uncertain recognition] ...