Lecture 7: Classical Protein Structure Prediction II
Recording. Download the text transcript.
Automatic transcript; technical terms and equations may contain recognition errors.
00:00:18 [Uncertain recognition] Okay, let's get started. Howdy!
00:00:20 [Uncertain recognition] Okay, welcome back to our ECEN 766.
00:00:26 So today's contents have a lot of subtopics.
00:00:31 Not that they are super important, but I think for your completeness of the knowledge,
00:00:38 I thought it's worthwhile including them.
00:00:42 And also we get a chance to talk about integer programming after linear programming.
00:00:49 So I thought that was useful.
00:00:51 But before going there, let's remind ourselves last time we talked about integer programming.
00:00:59 So did anyone see anything that's missing in this diet problems formulation?
00:01:08 No complaint?
00:01:09 There must be other constraints, I guess.
00:01:13 Pardon me?
00:01:14 There must be other constraints because when I solved this problem on Google,
00:01:19 they were going to other constraints as well.
00:01:22 So what are missing constraints?
00:01:24 Can you think of the problem statement that then?
00:01:27 Should it be negative?
00:01:28 Could you speak a little louder?
00:01:29 What should it be negative?
00:01:30 The decision variable.
00:01:31 The xi is the daily amount of the food i.
00:01:34 So that is non-negative.
00:01:35 Is that right?
00:01:36 Good.
00:01:37 So this x is non-negative.
00:01:38 Another thing we're asking is, again, remind yourself about this general formulation.
00:01:42 Minimize C transpose x and subject to the total value of the food i.
00:01:45 The total value of the food i.
00:01:46 So that is non-negative.
00:01:47 Is that right?
00:01:48 Good.
00:01:49 So this x is non-negative.
00:01:55 So that's one thing to add.
00:02:00 Another thing we're asking is, again, remind yourself about this general formulation.
00:02:08 Minimize C transpose x and subject to A x bigger than or equal to B.
00:02:16 I let this sign constraints, non-negative constraints, to be part of A.
00:02:22 And let's say x belong to n dimension and A belongs to m by n.
00:02:37 So we were saying that conceptually we could traverse the extreme points.
00:02:48 Right?
00:02:49 We could traverse the extreme points.
00:02:51 In the worst case, the last extreme point, if we don't repeat, the last extreme point in the worst case is the global optimum.
00:03:00 Right?
00:03:01 So that tells us what concept of an algorithm.
00:03:09 Time complexity of the algorithm.
00:03:11 Right?
00:03:12 So last time we were asking, well, if that's the case, right, how many extreme points or vertices are there for this polyhedron?
00:03:21 By the way, if the polyhedron is bounded, then it's called a polytope.
00:03:25 Right?
00:03:26 So how many extreme points or vertices are there if we need to figure out the time complexity?
00:03:34 Let's say there are m constraints and the decision variable is in the n-dimensional space.
00:03:42 How many extreme points?
00:03:44 So what we need to do is we need to do a vertex or extreme point.
00:04:01 Anyone?
00:04:02 How do you get a vertex or extreme point?
00:04:06 What do you need?
00:04:07 Needs what?
00:04:08 Intersection of some number of equality.
00:04:26 Right?
00:04:27 Equalities, right?
00:04:28 So in the terminology of optimization, we say that that constraint is active, meaning that it's
00:04:37 strictly equal, like, you know, the ice constraint, inequality, happens to be active.
00:04:44 So it means equality.
00:04:46 So that means some number of equalities needs to be simultaneously hold so that we see intersection or vertices.
00:04:56 Question is, how many?
00:05:02 How many inequalities needs to be simultaneously hold so that you get a vertex in the n-dimensional space?
00:05:11 Well, in the two-dimensional space, it's easy to see it's two.
00:05:22 In the n-dimensional space, how many equalities needs to be hold?
00:05:30 N.
00:05:31 Is there any requirement for this n constraints?
00:05:36 They shouldn't be, like, parallel?
00:05:38 Right.
00:05:39 They shouldn't be parallel or correlated.
00:05:41 In other words, they should be independent from each other, right?
00:05:44 So apparently, m has to be bigger than or equal to n, otherwise the system, you know, is under-determined, right?
00:05:51 So in this case, we need at least, out of m constraints, we need at least, we need exactly n independent inequalities to be active so that we can get an extreme point.
00:06:06 So in total, m choose n, assuming that m is bigger than or equal to n, right?
00:06:16 Then you can rewrite it as m factorial divided by m factorial divided by m minus m factorial.
00:06:23 And if you use a Stirling formula to approximate m or m factorial, you'll get some approximation of exponential terms.
00:06:32 So that's another follow-up, okay?
00:06:36 Okay, now let's start today's content.
00:06:38 As I said that there are a lot of contents today.
00:06:41 Some of them I'm telling you for the completeness.
00:06:44 Some of them I think more important as we continue from linear programming to integer programming.
00:06:50 I mean, you see that the ability to formulate a problem is very critical, okay?
00:06:59 We will see a formulation at the end which is very difficult even to read.
00:07:04 Then you wonder how you come up with that, right?
00:07:08 Let me remind you where we are.
00:07:11 We are in the classical protein structure prediction problem.
00:07:15 We are in the safe zone, very safe.
00:07:18 What do I mean?
00:07:19 What I mean is that there are template sequences who are so similar, more than 30%,
00:07:24 that we are almost sure that their structures can be directly borrowed.
00:07:28 Okay, this is called a homology modeling approach.
00:07:31 There are two sub-problems that we are talking about.
00:07:34 One is if we know the template, how do we know what positions or residues of the template sequence should be aligned to what positions or residues of the query sequences?
00:07:45 So that we know which part of the template structures can be directly borrowed, which part needs to be inserted or deleted or modified.
00:07:54 So that was our question, right?
00:07:56 So that problem is essentially a sequence alignment problem and it's solved by dynamic programming.
00:08:03 It's exact.
00:08:05 And the time complexity and the space complexity are in the order of m times n, right?
00:08:12 So that's the Needleman-Wunsch algorithm.
00:08:15 So since more people are here, we actually have assigned the first homework.
00:08:20 So you can check on Canvas.
00:08:22 It's under the module for this week.
00:08:26 You have two problems in that homework.
00:08:29 One, the first one is to get familiar with the PDB format, the structured data.
00:08:35 And I'm asking you to plot by yourself the Ramachandran plot and see the different amino acids patterns are different and explain a little bit why you see such pattern difference.
00:08:47 The second question is implementing the Needleman-Wunsch algorithm by yourself and align two pairs of sequences, okay?
00:08:55 And tell which ones are more similar to each other.
00:08:58 So these are the two homework questions.
00:09:01 And you're going to submit the homework in PDF or .c or .py directly on Canvas, okay?
00:09:09 So if you have any other questions, please let me know.
00:09:12 I will also send another announcement through Canvas.
00:09:17 Did I say eCanvas?
00:09:18 Canvas.
00:09:19 And you will get an announcement as well, okay?
00:09:24 Any questions, you have two weeks to finish the two questions.
00:09:27 Should be relatively straightforward implementations of the algorithms, okay?
00:09:34 So today we have two parts.
00:09:38 The first part is we're going to finish the safe zone by looking at the second problem.
00:09:45 Because, you know, once we know what's the template, we can do the alignment with order of N squared, right?
00:09:52 But where do you find the template?
00:09:54 So we're talking about the template identification problem, and this approach is basically a database search, okay?
00:10:01 So for a lot of methods, I'm talking about, I don't, I'm not asking you to, you know, remember what they do,
00:10:07 but I'm asking you to sort of, you know, not observing how they are done, but actually think about why they are done in that way.
00:10:14 Because this is a perfect training examples for you to do your own algorithm development, okay?
00:10:22 So in these cases, I'm going to mostly, you know, help you think about how you should address these problems algorithmically, okay?
00:10:32 And I put in the square bracket that I'm going to give you additional slides, if for some of you who are interested in how to do the whole homology modeling business,
00:10:41 I have additional slides already included, but they are with these square brackets to show that they are optional and for your completeness of knowledge, okay?
00:10:51 Okay, so, and also put, you know, if you want to know more, chapter 31 of Goo and Boom contain this information.
00:11:02 Okay, now here we are, we are first right here, okay?
00:11:07 So this is a classical structure prediction, and the rationale is how much we can leverage homology data.
00:11:13 We know that in the safe zone, we can leverage the template structures because their sequences are so similar, okay?
00:11:22 So let's talk about template identification problem.
00:11:25 So what's the problem?
00:11:29 You told me that for any given template sequence, I could use Niedermann-Wunsch algorithm with a decent time and space complexity and find their optimum alignment.
00:11:44 Well, why is there any question that remaining?
00:11:48 I can simply apply the Niedermann-Wunsch algorithm to every pair of template, potential template, and the query sequence, right?
00:12:00 If you have a million templates, I just do it a million times.
00:12:03 Why is there a problem?
00:12:05 Sequence length is too much, so...
00:12:09 Sequence length is too much, it's in the order of N-squares, yes.
00:12:12 When N is large, this could take minutes or hours evenly, right?
00:12:18 But more importantly, the database is large, right?
00:12:22 So even we're talking about 180,000 structures, but if we remove the redundancy in the sequence or structure space,
00:12:29 we may still talk about, you know, 10 to 4-ish structures.
00:12:34 So doing that 10 to 4 times, right?
00:12:38 This, you know, this hours or tens of minutes is still not an idea, right?
00:12:45 You think about it every day, this NCBI blast, this web server for sequence alignment, except how many queries do you know, right?
00:12:55 So you cannot even sustain that kind of service.
00:12:57 So that means this naive approach, just by, you know, enumerating all the pairs is not possible anyway, right?
00:13:08 If you think about how we smartly improved the sequence alignment, we also avoided enumeration, right?
00:13:15 We avoided enumeration, we figured out that we can break the bigger problem recursively into smaller and smaller problems, right?
00:13:24 And the bigger problems optimal solution can be built upon the smaller subproblems optimal solution.
00:13:31 That's how we figured it out, right?
00:13:33 So similarly here, we can do something similar as well, in the sense that we don't try to enumerate,
00:13:40 but we know when to pay attention and when we can throw away such candidates for templates, right?
00:13:48 So how do you accomplish that?
00:13:51 The general idea is that you are looking for a fast but heuristic.
00:13:57 By heuristics, what I mean is that, you know, it doesn't really guarantee you the accuracy, okay?
00:14:03 You will have to sacrifice some accuracy, but you're going to gain the speed.
00:14:08 You're going to gain the speed, okay?
00:14:10 So how do we really, yes, we can gain speed and by sacrificing a little bit of accuracy without, you know,
00:14:20 guaranteeing the best template and the best alignment with that best template.
00:14:26 But what can be done?
00:14:28 Well, if you think about a database of templates, maybe 10 to 4,
00:14:35 maybe less than 0.01 or, you know, 0.1% of the templates are really valid template candidates, right?
00:14:47 They are very similar probably.
00:14:49 Most of the time you are doing what?
00:14:52 If you take the naive approach, 99.9% of the pairwise alignment by dynamic programming is wasted to very dissimilar sequences or regions that are very dissimilar.
00:15:05 So that means somehow we have to tell that those majority, 99.9% are dead ends that we can throw away.
00:15:18 And we need to figure out that there are dead ends before we do the complete dynamic programming, right?
00:15:25 So that's the idea, okay?
00:15:27 Or in other words, if you don't try to figure out which are dead ends, you can also inversely figure out which ones are really promising and only focus on those.
00:15:38 Either way, right?
00:15:40 So how do you do that?
00:15:41 The idea is, you know, is very simple.
00:15:44 The key insights is that, you know, if two sequences are very similar to each other, if we are talking about a global pairwise alignment, they must share some substrings or subsequences that are very similar or identical.
00:16:01 So that's a key observation, okay?
00:16:04 So that's why if you talk about, you know, the most cited papers in the last century or even until the first 10 or 20 years of this century, one of the papers is this tool, BLAST for basic local alignment search tool.
00:16:27 As you can see from the name, it's a database search tool.
00:16:31 And it's for local alignment.
00:16:34 As long as you have some sub sequences or regions that can be identified, commonly shared, then that's fine.
00:16:43 So that's first developed actually more than 30 years ago.
00:16:49 It's one of the top 10 most cited papers.
00:16:53 So what it's trying to do is first, you know, we try to compile a list of words for query and then scan the sequences in the database for hits.
00:17:05 So if they see whether this potential candidates for templates contain those words, okay?
00:17:13 If they do, that's a hit.
00:17:15 Then you gradually extend the hits from the shorter sequences or words gradually into longer and longer words, right?
00:17:26 Because you are trying to do the local alignment.
00:17:28 You try to find the bulk of regions that are similar, similarly shared, okay?
00:17:34 So, again, this is very simple ideas that, you know, I thought for, in general, this is something that quite classical approach, right?
00:17:46 What you do is first, as I said, if you have a query sequence, you can break them into words, like a kmer, here k equal to three, right?
00:17:56 k consecutive letters, right?
00:18:00 And they could be overlapping, right?
00:18:02 And then they are, these are words, right?
00:18:04 In the meantime, you can also break the database sequences into words as well, right?
00:18:10 Then you are basically querying these words, right, in the database to find whether there's a hit, right?
00:18:18 So, scanning for hits is a relatively classical problem.
00:18:25 What they are trying to do is basically compare two word lists.
00:18:29 One is a query word list and one is a database sequence, database word list, right?
00:18:35 And you try to find the occurrence of a list of words in a sequence, right?
00:18:41 This is a classical problem, right?
00:18:42 When people first try to study, you know, literature from a statistical point of view, they try to see what words are used at what frequency by Shakespeare versus others, right?
00:18:55 And these, what approaches can be used?
00:18:58 You can use hashing, right?
00:19:00 This is a very classical algorithm.
00:19:03 Or you can use a faster algorithm such as deterministic finite automation or finite state machine, okay?
00:19:11 Once you've figured out that, oh, these query words do have hits in the template sequences, then what you need is, you know, grow these short words into longer and longer regions, right?
00:19:28 This is called hit extension, so you want to extend these words on both sides, right?
00:19:35 For instance, you may have a four-letter word, srsk, being shared between the query, between the query words and the database words.
00:19:47 And this is a sequence from the database that contains that query words.
00:19:52 Then you want to see whether I can grow this word in two directions so that this matching can be extended.
00:20:01 For instance, I can go this direction by extending from k to g, e, p, then I realize that, oh, this is perfectly fine for the query sequence as well, right?
00:20:12 So I can extend this word left or right to make it longer, right?
00:20:17 Eventually I figure out that this is a maximum segment.
00:20:20 Why do I care about a maximum segment?
00:20:22 That's because I'm doing the local alignment, not the global alignment.
00:20:27 I just, I'm interested in the commonly shared sub-regions, okay?
00:20:33 So another one is called a PsiBLAST.
00:20:38 PsiBLAST.
00:20:39 BLAST is able to help you, remember, it's a fast heuristic.
00:20:44 It helps you find the homologs, but it could miss something, okay?
00:20:51 So PsiBLAST makes sure that even if the homology or the relatives are distant, you can still find those distant homologs.
00:21:02 That's what PsiBLAST is doing.
00:21:04 But the reason I'm introducing PsiBLAST contains another layer, that is, I want to tell you something called profiles or position-specific scoring matrices or profiles.
00:21:16 This concept is very important as we step away from the safe zone to the twilight zone, okay?
00:21:26 So this is called the position-specific scoring matrix.
00:21:29 So in the homework, when you do the pairwise alignment, you're not going to use a plus one, minus one simple scoring matrices.
00:21:38 You're going to use something called BLOSSUM62.
00:21:41 I introduced this with a slider, but I put a square root bracket so you can read that.
00:21:46 But you can also download this BLOSSUM62 for the substitution matrix, right?
00:21:53 What is the difference or similarity between A and G or T and V?
00:22:01 These are amino acids, okay?
00:22:05 So what PsiBLAST is better at than BLAST is that it's more sensitive, okay?
00:22:12 So it's not using the predefined scoring matrices like BLOSSUM62.
00:22:18 It's actually building a position-specific scoring matrix specifically for the query protein, okay?
00:22:25 So in the case of BLAST, it's always using a fixed predefined scoring matrix like BLOSSUM62, right?
00:22:33 The similarity between A and G is always the same.
00:22:36 But in the case of PsiBLAST, it builds a position-specific scoring matrix, okay?
00:22:42 Specific to the position, specific to the protein family.
00:22:46 I will talk about it.
00:22:47 So this means it's more sensitive to find distantly related sequences that are often missed in the BLAST search.
00:22:55 So what is a position-specific scoring matrix?
00:23:01 Well, you can think of it as some kind of probability mass distribution, okay?
00:23:07 So previously, you heard about, you know, the notion of describing a sequence in this case.
00:23:17 a nucleotide sequence as a sentence written in a lot of letters, right?
00:23:24 So at each position, you have one letter.
00:23:27 So in some sense, if you regard each position not as a fixed letter, but regarded as a random variable,
00:23:38 which can take 20 plus one values, that one is the gap, that 20 is amino acid.
00:23:44 Then you can think of each position contains a probability distribution, right?
00:23:51 If you use C and G and disregard the other possibilities, then you have a probability that is, if it's ACGT, then it's what?
00:24:01 0, 1, 0, 0, right?
00:24:04 0, right?
00:24:05 And then this is 0, 0, 1, 0, right?
00:24:10 So just, you know, there is a 100% for some letter, right?
00:24:14 But what if, what if you can change that, right, into a distribution?
00:24:21 So it's not like a single letter is taking 100% probability.
00:24:26 The way you do it is constructing a profile like the following.
00:24:30 You first do a multiple sequence alignment, okay?
00:24:34 You may say, well, wait a minute, you told me what is, you know, pairwise sequence alignment, right?
00:24:40 And now you're talking about a multiple sequence alignment.
00:24:45 So how do you do that?
00:24:46 So you can do it in different ways, the slide that I skipped.
00:24:50 You can do a lot of pairwise and then stack them together or other ways, right?
00:24:55 And there are tools for you to do that.
00:24:57 Once you do the multiple sequence alignment, you basically put a family of homolog sequence together in the aligned way.
00:25:07 Okay? So every position is aligned.
00:25:11 And then you can count for each position what's the frequency of every letter, right?
00:25:19 Right? And then if you're looking at C, G, I, for instance, right?
00:25:26 And we are looking at the position, so for every position, right, we have a scoring matrix, right?
00:25:33 In this case, for instance, for column J, right, is a position J, right?
00:25:47 And I is the amino acid or nucleotide, right?
00:25:52 So there are 20 plus 1 or 4 plus 1 in the case of proteins or in the case of DNA, right?
00:26:00 And the number of columns or J is the number of positions, right, or length of the protein.
00:26:07 Then we can calculate the frequency FIJ based on the simple observation statistics, right?
00:26:15 Every column there is a frequency, right?
00:26:17 They add up to 1, okay?
00:26:19 Then we have to do one thing, right?
00:26:22 We have to normalize that frequency because you see here that, oh, there is a 75% and there is a 25% here.
00:26:32 Is it high or is it low, right?
00:26:36 By looking at the absolute frequency at this position, we have no idea, right?
00:26:42 So we can normalize that frequency which is position specific, J dependent, by a background frequency for this amino acid I, regardless of position J, okay?
00:26:56 So you can look at all these families, for instance, we have a lot of A, 1, 2, 3, 4, 5, 6.
00:27:02 There are six A's here.
00:27:04 So A is already over-represented in this family, right?
00:27:09 So seeing like at some position A contains, constitute 75% or 50% is not a big deal for this family, right?
00:27:20 So in this case, you normalize the frequency observed position specific frequency by the position, you know, independent background frequency for that amino acid.
00:27:35 And then you take, this is called what?
00:27:38 Odds, right?
00:27:39 Right?
00:27:40 Frequency divided by the background, right?
00:27:42 That's called the odds.
00:27:43 And then you take a log.
00:27:45 This is a log odds basically, isn't it?
00:27:47 Right?
00:27:48 So I didn't talk about the slides, for instance, how the blossom or PAM is constructed.
00:27:54 That's also very similar.
00:27:55 They also use log odds, but back then they didn't consider the positions and so on, okay?
00:28:01 So in other words, now you can think of this protein sequence not as individual protein sequence, but it's not like every position you have a single letter.
00:28:12 It's not like every position.
00:28:13 It's not like every position.
00:28:14 Now you have a probability distribution over 20 plus one letters if you are in the world of proteins, isn't it?
00:28:21 Right?
00:28:22 So this is called the profiles.
00:28:24 It's sort of generalized sequences, okay?
00:28:28 It's not saying that what is the letter at position one or two or three for this sequence, right?
00:28:34 It's actually reflecting what's the chance of the letter a, c, g, t at each position given this family.
00:28:42 Okay?
00:28:43 So that is what the profiles means.
00:28:46 So profiles are generalized compared to sequences, right?
00:28:51 It's, you know, a distribution instead of the fixed points.
00:28:56 That's the big deal, okay?
00:29:00 So then how do you use the profiles that are supposedly more sensitive to discover the distant homologues or relatives?
00:29:11 It's very simple.
00:29:12 Let's regard like there is, you know, some kind of three-dimensional mapping of a protein universe, okay?
00:29:20 They map it through the alpha, beta, or alpha-beta structures, okay?
00:29:25 Then imagine that you start, you know, you start with some kind of query sequence here, okay?
00:29:35 And then you look around, right, build a multiple sequence alignment, and I'm sorry, first of all, at the beginning, you have no idea, okay?
00:29:45 You have no priors.
00:29:46 The only prior for your scoring matrix is probably Blossom, right?
00:29:52 You can use Blossom 62, that is position independent.
00:29:55 Then using the Blossom, you look around, and this circle basically tells you what similar sequences you can see, okay?
00:30:05 You will miss some remote homologues, right?
00:30:09 You will miss some remote homologues, but very close homologues will be seen here, for instance, okay?
00:30:15 Once you have accumulated the initial family, now you can build profiles or position-specific scoring matrix.
00:30:26 Based on this, right, you will replace Blossom 62 now by the first step profile.
00:30:33 And then using that new scoring matrix, maybe you are able to find these more distant homologues in step two, right?
00:30:43 Now you expanded your family, right, from step one to step two, and you can update your scoring matrix, which probably allows you to find even more distant homologues going this way, right?
00:30:59 In the end, you probably are able to find the whole protein family for that query sequences.
00:31:04 So that's what the iterative search is for.
00:31:08 So if you think about what CyBLAST is called, right?
00:31:11 CyBLAST is called position-specific scoring.
00:31:16 PS stands for position-specific and IS stands for iterative, okay?
00:31:23 So position-specific tells you they are using profiles instead of family-specific profiles, instead of the predefined Blossom.
00:31:33 And then this profile is actually iterative, okay, updated.
00:31:37 So that's what CyBLAST is doing, okay?
00:31:42 So if you're interested, the sequence comparison does not always have to be based on alignments.
00:31:50 There are alignment-free methods if you're interested in them.
00:31:53 And sometimes you may desire to do that without alignment, and the problems, the reason of doing that without alignment are listed here.
00:32:05 So if you're interested, I list this in the slides for completeness.
00:32:09 Bless you.
00:32:10 And I'll also give you the whole appendix because now I have introduced the two key questions in the safe zone, right?
00:32:18 Finding the template using the database search, including CyBLAST.
00:32:22 And then doing the pairwise alignment between the identified template and the query sequence by using dynamic programming.
00:32:30 Then in the end, you are able to build the structure because that's your end goal.
00:32:34 So I give some additional slides if you are interested in, right?
00:32:38 So again, we follow the order of database search, and then we find a template, and then we align, and refine the align, and then the common parts are taken from the structure, right?
00:32:54 But then we have to insert loops, right?
00:32:57 That's the insertion or delete something or refine the structure all over.
00:33:01 And there are tools for you to do that.
00:33:04 Again, these slides are included for completeness for those of you who are interested in it.
00:33:10 You can take a more look into these, okay?
00:33:22 Okay, so with this, I'd like to finish the first part.
00:33:25 I think we are done for the safe zone, okay?
00:33:28 So in the safe zone, we see that we are solving these two kinds of problems, right?
00:33:34 The problem that remains is, you know, we know the steps that we identify the template, generate the backbone based on the identified template structure, and which portions are aligned.
00:33:47 And then we insert the loops, and we add the side chains on top of the backbone, we optimize the model, and validate the model, including Ramachandran plot, right?
00:34:00 What problem remains?
00:34:02 The problem is that the safe zone is safe.
00:34:05 It's easy to operate.
00:34:09 But the problem is that the safe zone is too small, okay?
00:34:14 75 to 35% of the genomes are estimated to be outside of the safe zone, okay?
00:34:21 It's a wide estimation from 75 to 35, up to 75%.
00:34:27 There's no accurate estimate.
00:34:29 But up to 75% of them are not, you know, operatable in the safe zone.
00:34:35 So the safe zone is too small.
00:34:38 So then we have to go beyond that.
00:34:41 In the twilight zone, right, the sequence similarity is high but not high enough to enable the homology modeling.
00:34:50 We are doing the threading, right?
00:34:52 We are saying that these similar profiles must have similar folds rather than saying that the similar sequences must have similar structures.
00:35:02 They are not that similar sequence.
00:35:04 But they are similar in the generalized sequence called profiles.
00:35:09 So then they have similar folds rather than similar structures because structures are more unique compared to the folds.
00:35:17 When you have, when you are in the, you know, midnight zone when the sequence similarity of the, you know, most optimistic case is so low, then you probably cannot use template at all.
00:35:31 And you have to use up initial approach, okay?
00:35:34 What alpha fold and other methods have revolutionized is how we view the problem, actually.
00:35:41 Because at early days we think that we need a global sequence homolog, then we borrow their structure.
00:35:47 Then threading and other methods tell us that we can break them into fragments and use naturally observed fragments and assemble them.
00:35:55 So at the fragment level or at the fold level, they are still similar, right?
00:36:00 But what alpha fold tells us is that, you know, there are other, you know, less apparent patterns that can be discovered by these deep learning models.
00:36:10 So the similarity probably is no longer defined by what we are looking at, for instance, sequence identity.
00:36:17 Okay, I think that's what the revolution is about.
00:36:21 Okay, back then the whole three scenarios are based on our observation that if sequences are similar enough, more than 30%, then their structures are similar.
00:36:31 So that guided all these developments, right?
00:36:34 But apparently more advanced models may be able to discover less visible or apparent patterns that can be utilized, okay?
00:36:46 So now, and there are a lot of structure prediction efforts using homology modeling or beyond, right?
00:36:59 For instance, when the outbreak of SARS-CoV-2 in the early 2020, so a lot of efforts were paid.
00:37:10 And there's some, you know, illustration of using BLAST, using PDB, using PIMO, using homology modeling and do some drug discovery.
00:37:19 It stopped update probably 20, you know, later that year, but it's a great showcase of citizen scientists or, you know, cross-discipline scientists, right?
00:37:34 So you can see how you actually use this for discoveries in a difficult timing.
00:37:41 So now I'm moving on to part two.
00:37:45 Any questions before I move to part two?
00:37:48 Okay, now I'm moving to part two, okay?
00:37:53 We said that previously in the safe zone, if the sequence identity is so large, more than 30%, they almost guarantee the similar structure.
00:38:03 So I can use homology modeling.
00:38:05 I can break them into two optimization problems and using dynamic programming or heuristics like PsyBLAST, okay?
00:38:15 Now, we're entering the twilight zone when the sequence identity is 20 to 30%, okay?
00:38:25 The difficulty here is that you may have a lot of templates whose sequences are 20 to 30% identical to the query sequence.
00:38:38 But some of them have very similar structures to the query protein.
00:38:43 Some of them have very different structures to the query protein.
00:38:47 By just looking at the sequence identity, you have no idea which one is of similar structures or which one is not.
00:38:56 That's a problem, okay?
00:38:58 So in other words, the sequence identity signal is not enough to tell us in a high resolution whether structures are similar.
00:39:09 That's a problem, okay?
00:39:11 The sequence level signal is not high enough.
00:39:17 It's too low to sustain the structure similarity, right?
00:39:22 So we're going to talk about how to solve this problem.
00:39:28 I'm going to ask you a question basically is what can we do?
00:39:36 What can we do, right?
00:39:39 What can you do?
00:39:42 Data, principle, what can we do with data?
00:39:48 You either use new data or additional data or use your older data more smartly or both, right?
00:39:58 That's all you can do with the data part, right?
00:40:02 Of course, your model can be accordingly modified and so on, right?
00:40:06 For the principle, you, of course, can use that to guide the design of the model and so on, right?
00:40:13 So I'm asking you the following question, right?
00:40:17 In this case, what data hasn't been used and can be used?
00:40:24 Let's start with the earlier question.
00:40:26 What data has been used so far in the case of the safe zone homology modeling?
00:40:32 What data has been used?
00:40:36 That's the criteria.
00:40:37 What data has been used?
00:40:40 So you have a query sequence, right?
00:40:43 And you have what?
00:40:45 A database of potential, a sequence database of potential candidates.
00:40:52 Potential candidates for the template, right?
00:40:56 And then once you've figured out the template, you're going to use the structure of that identified template, right?
00:41:03 Did you smell something that hasn't been used so far?
00:41:07 Is there anything that we haven't used?
00:41:11 Let me remind you, for the template library, we compare all their sequences to the query sequence in the fast heuristics.
00:41:21 Once we figure out some good candidates, we're going to borrow their structure.
00:41:25 What data hasn't been used so far?
00:41:28 Structures.
00:41:29 Structures of what?
00:41:31 What data hasn't been used?
00:41:38 We used the structures of the identified templates.
00:41:44 Did we use all other structures?
00:41:48 We threw them away.
00:41:52 Because back then, we didn't need the help of those structures.
00:41:56 We just need the sequences.
00:41:58 And the signal is clear enough that if it's above 30% similar, we just look at that sequence and that structure.
00:42:05 Right?
00:42:06 We never needed back then in the safe zone additional help.
00:42:11 We just threw away those structures who are potentially different or who are not necessarily the ultimately identified templates.
00:42:22 Right?
00:42:23 So that's how you can solve the problem, actually.
00:42:27 Okay?
00:42:28 So we're going to talk about, again, two sub-problems, very similar to the safe zone.
00:42:36 First is, in the safe zone, remember, we had to align a query sequence to a template sequence.
00:42:44 Now, we're going to align the query sequence to the template structure or folds.
00:42:50 Okay?
00:42:51 This is additional data we never used.
00:42:53 Okay?
00:42:54 And it involves integer programming and linear programming.
00:43:01 We're going to talk about them briefly.
00:43:03 And then, similar to the safe zone, right, I was saying that once you figure out the template folds, right, you just align the query sequence to it.
00:43:13 But how do I find the folds, right?
00:43:15 You know, I know there are only 10 to 3, right, folds, much smaller than 10 to 5, or 10 to 180,000, 10 to 5 structures, right?
00:43:27 I know it's a much smaller number, but still, can I, you know, figure out which folds are the best?
00:43:34 It's like the database search problem we were talking about, right?
00:43:38 So that problem is more solved by machine learning nowadays.
00:43:41 You start with a sequence.
00:43:42 You predict which one of the 3,000 folds it belongs to or give a probability matrix.
00:43:48 I put it in the light gray to show, to just say that, you know, I'm not going to talk more details about it because I will finish the structure prediction problem and talk about the numerical optimization.
00:44:01 Then I will start talking about machine learning using protein function prediction.
00:44:05 Okay?
00:44:06 So that part I will not emphasize.
00:44:08 So now let's start with our Twilight Zone, okay?
00:44:13 What's the motivation here?
00:44:15 There are two observations that lead to the so-called threading algorithm in the safe zone.
00:44:22 One is the fact that we showed before, over the years, right, you look at the new folds every year in blue, or the cumulative growth in red,
00:44:34 we sort of see a saturation, right?
00:44:38 There's a small number of protein folds, seemingly, which summarize the pattern of the secondary structures in the structures, right?
00:44:48 That number is small and seems to reach a saturation.
00:44:52 So that's good.
00:44:53 So I may not know exactly what's your structure, but the next best thing is probably its fold, right?
00:45:00 It's like the pattern of the structure, okay?
00:45:03 So with that observation, we talk about the Twilight Zone.
00:45:10 The method is called threading.
00:45:12 Exactly is what I'm trying to say here is that what additional data can you use?
00:45:17 We previously did not use any potential template structure except the templates we eventually identified, right?
00:45:26 So the additional data is the structure information in the database, okay?
00:45:32 So in other words, if there are only 3,000 folds, right, in nature and most likely we have seen all of them, then we can ask, can we kind of, you know, look at the query sequence, right?
00:45:49 And then, in the regard like a string or, you know, like a string, and then if we have like 1,000 folds, can we thread each, sorry, can we thread the query sequence to each of the fold and see how the query sequence likes the fold or not?
00:46:08 Or how much they like it, okay?
00:46:11 So that's the threading.
00:46:13 In other words, you are aligning not two sequences, but you are aligning the target sequence onto the 3D structure.
00:46:23 In this case, it's one of the folds.
00:46:28 Any question?
00:46:30 Any question?
00:46:31 So this is the additional data we are using, and the way we use the data is try to align the query sequence, right?
00:46:39 Like to thread the sequence onto the structure, and there are 3,000 of them.
00:46:44 And then we can figure out whether the sequence is a good fit to the structure based on the local structure, environment, and pairwise interactions.
00:46:54 These are like the objective function that we can talk about later on, okay?
00:47:00 So we said that, you know, you may wonder why can I use BLAST or CyBLAST to find the fold, you know, instead of doing it for all of the folds.
00:47:15 The problem is that, you know, even CyBLAST is better than BLAST in discovering the distant homologues, but in our case, we are in the twilight zone.
00:47:24 It's even a tougher situation that CyBLAST is not perfect.
00:47:30 Okay, any question?
00:47:32 Okay, with this idea in mind, then what remains to be done is how we align a sequence to a structure.
00:47:43 We know how to align sequences, right?
00:47:47 How we align a sequence to a structure, right?
00:47:51 What are your thoughts?
00:47:53 What's the first thing you have to do is to represent the structure in some way that is friendly to be aligned to a sequence.
00:48:03 Is that right?
00:48:05 So, let's talk about threading.
00:48:08 There are three key components of threading, exactly the three for optimization.
00:48:14 Decision variable, objective function, and search algorithm, okay?
00:48:19 The decision variable, just like the sequence alignment, is about which residue in the query sequence to align to which position or residue in the template fold, right?
00:48:33 This is the decision variable.
00:48:35 So, the variable.
00:48:36 Related concepts or barriers you have to overcome is how do you represent the query or the target, right?
00:48:48 A sequence or profiles or more that you have learned, right?
00:48:53 And you may eventually use a different algorithm, but you know, you have to start with the representation of the target.
00:49:00 Then you need to have a library of template folds, and then you have to represent the template folds as well, right?
00:49:07 Then you align the representations of the target, right?
00:49:17 The objective function is to make sure that the sequence is a good fit to that structure.
00:49:24 So, it will, you know, it will involve some scoring that we'll talk about.
00:49:29 And lastly, among all possible alignments, right, which ones are the best?
00:49:38 That's the search algorithm.
00:49:40 We already knew from the sequence alignment that we cannot afford brute force
00:49:46 in the duration, which is, you know, giving us astronomical combinations, right?
00:49:52 Okay, now let's follow these three elements and start with the decision variable, okay?
00:49:59 Remember that to do that, we have to represent the query or the target sequence as well as the template folds, okay?
00:50:08 So, how do you represent a query or a target?
00:50:13 The easiest way is just look at the sequence alone, right?
00:50:18 Just a string.
00:50:19 But you have learned something more than that.
00:50:21 You can use the profile or the position-specific scoring matrix derived from multiple sequence alignment.
00:50:29 You can look at the profile instead of the sequence, okay?
00:50:33 It's not like a fixed point for every position, but a random variable with a distribution, right?
00:50:40 Probability mass distribution.
00:50:42 You can do more because now you are aligning a query sequence to a target sequence.
00:50:50 You can figure out, for instance, starting with a template sequence, what is the predicted secondary structure in three classes or eight classes.
00:51:02 Remember, we talked about this problem before.
00:51:04 One of the earliest application of machine learning in structure bioinformatics is predicting from the protein sequence, the secondary structures, right?
00:51:16 Remember, neural networks was used back then before I was born, right?
00:51:20 So, you can use that one.
00:51:24 And then you can also use the predicted solvent accessibility, whether each residue is at the core or at the surface or somewhere between.
00:51:34 So, all these are sequence, evolutionary, secondary structure, and solvent exposure, right?
00:51:45 So, these are the different contexts.
00:51:47 You have the sequence context.
00:51:49 You have the evolutionary context across the whole family.
00:51:52 And then you have the structural context, whether it's a secondary structure or the solvent accessibility, right?
00:51:58 Because predicting the secondary structure is much, much easier than predicting the tertiary structure.
00:52:04 Of course, arguably, you can say that predicting the tertiary structure after alpha fold is easy, but still, right?
00:52:12 So, potentially, if you're redoing this, maybe you will use the actual structure even.
00:52:17 So, this is how to represent a target, as I said.
00:52:21 Sequence, evolutionary profiles, and structural context predicted, okay?
00:52:27 We only have the predicted, okay?
00:52:29 Remember, the query sequence have no structure, right?
00:52:33 But the structural context, like a secondary structure or solvent accessibility, very easy to predict.
00:52:41 Now, how to represent a template?
00:52:46 I first have to select templates, right?
00:52:49 To construct a library.
00:52:51 So, for any library, you need it to be sufficiently diverse, no redundancy.
00:52:59 In the meantime, the union of them should be inclusive, right?
00:53:03 They should be diverse and inclusive in both the sequence and the fold space, right?
00:53:10 So, what people usually do is, for instance, in this paper, they cluster the entire PDB into the representative families at a level of 35% global sequence identity, right?
00:53:22 As you see in the homework question one, PDB actually gives you such clusters, which are updated on the database, okay?
00:53:33 So, getting the template library is, you know, done in this way.
00:53:40 Once you have the template, you have to represent the template, right?
00:53:44 So, just like the query sequence, you could have the sequence, you could have the evolutionary profile,
00:53:52 and now you have the actual structural context because these templates have structures, right?
00:53:59 You can have the actual secondary structure and actual solvent accessibility, right?
00:54:05 And you can even do some structure-based profiles.
00:54:08 Doing not multiple sequence alignment and get the profile, you can do the multiple structure alignment, okay?
00:54:13 But if we forget about this, and all these representations here are 1D.
00:54:21 By 1D, I mean what?
00:54:24 I mean every position is featurized by different features, okay?
00:54:31 So, I don't have the pairwise features.
00:54:33 I only have the feature for every position.
00:54:36 It's like a 1D.
00:54:37 So, in other words, you know, it's one dimension for the sequence and 21 dimension for the profiles.
00:54:46 And then if there are three classes of secondary structures, then that's three dimensions for the secondary structure.
00:54:53 If there are three levels of solvent accessibility, that's three again.
00:54:56 So, the total number of features is like 1 plus 21 plus 3 plus 3, okay?
00:55:03 So, if every row is a position, then, I'm sorry, if every column is a position, then you have 1 plus 21 plus 3 plus 3 rows.
00:55:22 These are the number of features you have, okay?
00:55:24 That's your feature matrix.
00:55:25 So, before we talk about additional representation,
00:55:31 Now that you know, both templates and sequences, I'm sorry, yeah, query sequence and the template folds can be represented in 1D, right?
00:55:46 Do you have an algorithm to align them?
00:55:55 Have you learned an algorithm to align them?
00:55:58 The only difference is in the past, you only consider sequences.
00:56:02 Now you have sequence, profiles, and structural context.
00:56:07 Are you able to align them?
00:56:09 We need a big score based on sequence and structure.
00:56:17 Yes.
00:56:18 Let's say you have a score, right?
00:56:20 For similarity between different secondary structures or profiles and so on, right?
00:56:27 And it's just like the sequence alignment is pairwise additive, okay?
00:56:34 For every pair of positions, we add the similarities together, right?
00:56:40 Any ideas?
00:56:41 Yeah, we can use the same algorithm.
00:56:44 Same algorithm as?
00:56:45 Same algorithm as?
00:56:46 Sorry, in the last section, if we have the scores for the similarities.
00:56:51 What struct?
00:56:53 Last?
00:56:54 Like, the algorithm that can give us.
00:56:57 Oh, you said BLAST?
00:56:58 I see.
00:56:59 We're talking about the pairwise alignment for now.
00:57:02 Yeah.
00:57:03 Not the database search.
00:57:04 But you're right.
00:57:05 So let's keep that question in mind, and I will talk about the answer right away, okay?
00:57:13 But there's also more information in the template, because the template has a structure.
00:57:21 What we have had so far from the actual secondary structure and solving accessibility is like,
00:57:28 you know, if you think about the protein structure, it's like a point cloud, right?
00:57:34 What we have here is like a marginalized distribution for every position, right?
00:57:41 We are throwing a lot of higher-order information.
00:57:45 For instance, right, whether residue i is close to residue j, so-called contact.
00:57:52 This is, you know, two-body or pairwise contact, or multibody, i, j, k, interacting in the cluster.
00:58:00 Those kind of higher-order information than 1D are not considered, okay?
00:58:05 So let's also keep that in mind, okay?
00:58:08 Because usually when you want to improve your algorithm, you've got to be able to rationally construct that, right?
00:58:15 Either you use more data or use the data more smartly or both, right?
00:58:21 So the second element is the objective function like Salman was asking.
00:58:30 And we can do a lot of weighted sums, okay?
00:58:33 So again, we are summing over all the aligned positions.
00:58:37 For each aligned position, we can do a weighted sum based on the sequence or profile similarity,
00:58:44 or the environmental fitness score, or the structure consistency, like whether the secondary structures or the contacts are preserved.
00:58:54 And then we can also have a gap penalty, like what we do in the sequence alignment, okay?
00:58:59 So with the decision variable and its objective functions more or less figured out,
00:59:05 we have to talk about the algorithm, right?
00:59:08 Because we need to overcome the combinatorial explosion.
00:59:14 So if you only represent the template by the 1D representation,
00:59:21 then you can use the same dynamic programming to align a query sequence to a template structure, okay?
00:59:31 It's still polynomial time, you can still use dynamic programming, okay?
00:59:36 So this is one of the earlier methods, called master, they use dynamic programming.
00:59:40 But, so in that case, you can have polynomial time algorithm, right?
00:59:47 Including dynamic programming, that's order of m times n, right?
00:59:51 Or n squared, if m equals to n.
00:59:54 But, if you use 2D representations like contact map,
01:00:00 include it, then the problem gets MP hard, meaning non-deterministic polynomial time hard.
01:00:09 It's basically a way to define a class of optimization problems.
01:00:14 Roughly, you can think of there's no polynomial time algorithm, okay?
01:00:19 So, if you were in the age of seeing the threading algorithm,
01:00:28 including master, you naturally will ask,
01:00:33 what information have I not used yet?
01:00:36 Or what data have I not used yet?
01:00:38 So that if I use it, I can improve the accuracy.
01:00:43 So, I'm giving you one example.
01:00:45 What they see is that, oh, the 2D information in the template is not used yet.
01:00:51 So I can use that additional information and improve the performance, okay?
01:00:56 So, innovation is very important to us, but we also have to keep in mind that
01:01:03 it doesn't come easy, but there are certain ways to innovate, okay?
01:01:09 So, there is the scientific way to do science, okay?
01:01:13 So, in this case, retrospectively, it seems like a great idea, right?
01:01:18 You are trying to use more data.
01:01:20 You got to have, if this data is reliable, you got to have more accurate solutions.
01:01:25 And that's exactly what the Shoe group developed called Raptor.
01:01:32 We're going to talk about that example.
01:01:34 And it's using integer programming, okay?
01:01:37 I think now is a good time to talk about integer programming, right?
01:01:42 I'm going to borrow some slides, right?
01:01:45 So, integer programming, after we learned linear programming, means that the decision variables
01:01:53 are no longer continuous, but they could be, you know, just integers, right?
01:01:58 So, what does that mean?
01:02:00 We know that for optimization algorithm, we usually wonder whether it's convex or non-convex.
01:02:06 We know that that's a difference between, you know, easy and difficult optimization problems.
01:02:14 So, for linear programming, we know that the feasible set is convex and the objective function is convex.
01:02:24 So, you know, we have guarantee of the global optimum.
01:02:29 Some are slower, some are faster, okay?
01:02:32 But in the case of integer programming, do we have a convex problem or not?
01:02:40 Let's say the objective function is linear.
01:02:42 Everything is the same as linear programming, except that the decision variables are only integers.
01:02:48 No longer just continuous real numbers.
01:02:51 Are you going to say this is a convex or non-convex problem?
01:02:55 Who think it's convex?
01:03:02 Who think it's non-convex?
01:03:05 Okay, why?
01:03:08 The objective function is linear.
01:03:13 The feasible set is more of a set.
01:03:16 Yes, as Nami said, the feasible set contains a lot of discrete points.
01:03:22 If you connect two points, you know, very likely that most of the segment is not in the feasible set, right?
01:03:29 So, in other words, integer programming in general is MP-hard, okay?
01:03:36 So, let's talk about the formulation, which can be very interesting, right?
01:03:42 So, let's talk about how to translate the real-world problems, including constraint, right?
01:03:50 Into an optimization problem, okay?
01:03:53 In this case, it's a constraint.
01:03:55 So, if you select X1 equal to 1 if it's iPad, X5 equal to 1 is the course 6.041.
01:04:03 6 is Electro-Engineering and Computer Science at MIT, right?
01:04:08 Course 6.
01:04:09 So, if you select the iPad, you cannot select X5.
01:04:14 So, in other words, if X1 equal to 1, X5 cannot be equal to 1, okay?
01:04:19 So, that means if X1 and X5 are either 0 or 1,
01:04:24 right?
01:04:25 Out of the four combinations or, you know, the four points in the feasible set,
01:04:31 the one that's not allowed is this point.
01:04:34 You know, when X1 is equal to 1, this is 1, X5 cannot be equal to 1.
01:04:41 So, how do you formulate that constraint?
01:04:50 Our decision variables are X1 and X5.
01:04:53 What is the constraint that can express this constraint 1 in plain language?
01:05:04 Let's translate the plain language to mathematical formulation.
01:05:09 Anyone?
01:05:10 Pardon me?
01:05:12 Sum should be less than what?
01:05:15 Sum should be less than what?
01:05:17 Less than or equal to 1, alright?
01:05:20 Because when both are 1, the sum is 2, right?
01:05:25 So, basically, it has to be on lower left of this green line.
01:05:30 this green line. X1 plus X5 is less than or equal to 1. By the way, I ignored X1
01:05:36 and X5 being binary in all these slides, okay? This is by default because it's
01:05:41 integer programming, okay? Let's look at another example. Let's have price 1 and 2
01:05:49 being X1 and X2, okay? If you select X1, that means if X1 equal to 1, then you
01:05:58 must select X2. It means if X1 equal to 1, X2 has to be equal to 1. So in other
01:06:04 words, out of these four choices, this one is not allowed. When X1 is 1, X2 is 0.
01:06:13 That is not allowed because when X1 is equal to 1, X2 has to be equal to 1. So
01:06:19 this is the only feasible solution for X2 when X1 is equal to 1. Now, can we rewrite
01:06:28 the constraint mathematically? Again, you can pay attention to this green line, make
01:06:35 sure that we have to be above this green line instead of below.
01:06:45 Anyone?
01:06:48 subtraction.
01:06:53 Subtraction.
01:06:58 Which minus which?
01:06:59 2 or just 2 or just 2?
01:07:06 Yes, X2 minus X1.
01:07:09 Less than or equal to, bigger than or equal to something?
01:07:16 This line is X2 equal to X1, right? So if you're above it, that means it's X2 bigger
01:07:24 than or equal to X1. As you said, X2 minus X1 is bigger than or equal to 0. Right? So you
01:07:31 notice that these constraints are linear, just like what you see in the linear programming.
01:07:37 But the only difference is that you have the additional constraints that X1, X2 or
01:07:43 these decision variables are integers or binary in this case. Okay? If X1 and X2 are
01:07:48 between 0 and 1, then it's linear programming. Okay? Easy to solve. Now, last one. You must select one,
01:07:59 price or both. You cannot select none. In other words, you cannot let X1 and X2 be 0 at the same
01:08:10 time. I think everybody should know now after seeing it. Let's see. Do you want to give it a try? So the hint is that we have to be above the green line.
01:08:21 Yes. Pardon me?
01:08:41 Exactly. Equal to 1, right? So X1 plus X2 should be bigger than or equal to 1. You want to be above the line. Right?
01:08:51 It's really fun, right? So if you want to explore more, you can check this link. Actually, I just gave very simple examples.
01:09:01 Very simple examples. Okay? But I also have to emphasize that you could have other kind of formulations, but these ones are good because they are linear.
01:09:10 Okay? Right? Okay. Now let's talk about how Raptor introduced the additional information of 2D contact and do the threading.
01:09:23 Aligning the query sequence right up here to a template structure. Okay? So this is the template structure
01:09:39 and the query sequence. Okay? So we can, first of all, only look at the core, which are the stable secondary structures, alpha helix and beta sheets. And we can ignore those loops because the loops are less defining folds. Okay? The secondary structures, stable ones, so are the consecutive ones are called the cores.
01:10:04 We also know that the pairwise interaction between the cores, right? If the two cores are closed, then we have a solid arc.
01:10:12 That's the additional information in the template structure we wanted to use. Otherwise, we can just do the dynamic programming. Okay?
01:10:20 Okay? So that is a blessing, but that's also the challenge. Okay? Let's keep that in mind.
01:10:26 Then we have the sequence. Okay? The query sequence. And then let's assume that, for instance, you know, the core one's first position is aligned to this position.
01:10:36 Then the rest is very simply following that, you know, we just have the next few up to the length of the core one. Right?
01:10:43 So that is a very simple alignment. Right? This blue line is alignment of a core position to a sequence or query position. Okay?
01:10:55 Core of the template to a position on the query sequence. Okay?
01:11:04 Core of the template to a position on the query sequence. Okay?
01:11:05 Now, you see these dashed arcs. What are the dashed arcs? The dashed arcs are essentially very similar to the solid arcs in the template structures.
01:11:21 In the query sequence, we don't have structures and we don't know the actual context. But we are saying that if this query sequence feels okay to fold into the fold like this,
01:11:33 then it's 2D contact should resemble the solid arcs observed in the template structure.
01:11:42 So if that's the case, for instance, there is a contact between core one and core two, and I know that core one is aligned to these positions,
01:11:51 and core two are aligned to these positions, then I will have an interaction between the residues across the positions aligned to core one and core two respectively.
01:12:02 Okay? So that's the dashed line. It's a hypothetical. Okay?
01:12:07 So basically we are saying that we are going to use this additional information from the template. That's 2D.
01:12:13 And we think that, you know, we're going to see whether enforcing the similar 2D pattern in the query sequence is a good thing or a bad thing.
01:12:23 Okay? We're going to use optimization to find the best way to align.
01:12:27 Remember, these blue ones, these assignments, are not fixed. These are our decision variables.
01:12:33 Where to place the blue ones are our decision variables. Right?
01:12:37 And the dashed arcs enter the objective function. Okay?
01:12:42 It will also show in the constraint and objective function. Okay, so let's see.
01:12:50 Let's see. Well, our decision variable xil is binary. It's one if and only if core ci is aligned to target position l on the query sequence. Okay?
01:13:08 So for instance, this is core one aligned to position l here. Okay?
01:13:14 And when I say that a core is aligned to a position, I mean that the head of the core is aligned to that position.
01:13:22 Because the rest just follows. Okay?
01:13:24 So let's not get confused.
01:13:26 When I say the core is aligned to a position, core is on the template, fold, or structure.
01:13:33 It means that the head of that core is aligned to that position. Because the rest just follows. Okay?
01:13:40 That is our decision variable. Right?
01:13:42 We want to figure out the head of each core is aligned to what positions.
01:13:45 And there's another decision variable because we have to address this arcs or the 2D contact. Okay?
01:13:56 So if core ci1 is aligned to target position as l1 and i2 is aligned to position l2, we have a y.
01:14:08 Which basically gives the binary variable for the arc. Okay?
01:14:13 So if i1 is aligned to l1 and i2 is aligned to l2, then this, you know, y i1, l1, i2, l2 could be equal to 1. Okay?
01:14:27 So this is a familiar integer programming formulation like one of the examples we have seen. Right?
01:14:33 In other words, only if core i1 is aligned to position l1 and core i2 is aligned to position l2,
01:14:41 So could this y be 1? This y is the arc. Okay?
01:14:48 Now, the formulation is, first, the objective function is relatively easy.
01:14:54 I don't want to say too much about it. It's a weighted sum of mutation, fitness, secondary structure, and so on.
01:15:03 And...