Video 2-8: Motifs

0:02 We looked at one type of hidden messages which was just a gene a region in the DNA that codes for a protein. There's um connected to that I guess the bi biological backstory is a little more subtle but is um in computer sciency terms a stronger and more easy to handle hidden message and that's motives. I'm going to explain where where this comes from, what this is. Uh for that a little detour on why why it's interesting and that is the biological motivation.

0:35 Uh we talked I talked about genes being portions that code for a protein and then we talked about this uh process the the central dogma of molecular biology that the the the genes are translated to transfer RNA which then in the ribosomes is sequenced into proteins. And that's how we make all these chemicals that fulfill biological functions. Now, if that was the only thing, every cell that has the same DNA would have to produce the same proteins all the time, and it wouldn't really be possible to have the same gen genetic information and yet have different cells do different things. Uh, and so there must be some something else going on. And much of what's going on is called gene regulation which is uh I think the picture okay this the video is amoeba sisters again with their particular style but the content I think is uh at the right level and also accurate and the drawings are a bit whimsical. It's a switch that can turn genes on and off.

1:44 The way this works um is going to be explained in a bit more detail in in the video, but the kind of short version is the translation of a gene turning producing a copy of transfer RNA from the gene needs to start somewhere and there's a special molecule the RNA polymerase that binds to a certain starting part of the gene and then starts the trend the copying and if you block that kind of electromagnetic uh starting position by putting something else there, another molecule, then that translation is not happening. Or if you make that starting region more attractive by helping it attract polymerase with other molecules, you can actually generate more of the protein. And that's that's what this gene regulation in the simplest case is about. Let's um do the quick video here when I was a little kid I had this art teacher she had poetry which I love that I got into someday us and let it out but that's creative expression ourselves have expression too the poetry They can express genes. To express a gene means that a gene can be used to make something functional, often a protein. In our protein synthesis video, we talk about these steps. The gene, which is made up of DNA, can be transcribed into mRNA during transcription and then used in translation to make a polyeptide chain.

3:29 A protein is made up of one or more of those chains. But you know what? It's not doing that with every single gene. Not every gene is expressed. That's why the phrase gene regulation gets put with gene expression because the expression has to be regulated. A cell in the eye has no need for using a gene that codes for stomach acid. Even though the gene is present, it would be wasteful to express that gene and likely uncomfortable. Proarotic cells and ukareotic cells both have genes to express. Some differences though. Recall that proarotic cells just have the DNA in their cytoplasm. They don't have a nucleus. So transcription and translation all just happen here. Unlike in a ukarotic cell, there's no traveling of the DNA out of a nucleus. Nope. In proarotes, it's all right there together and can really both be happening together at the same time as there's no nucleus involved. For proarotes, a lot of the control of whether a gene is going to get expressed or not tends to involve or impact transcription.

4:31 Ukarotes also have gene regulation that involves transcription, although they'll have a lot of other times for gene regulation, too, that we'll get into soon. So, you might wonder, how does gene regulation involve or impact transcription? Transcription again is when an enzyme called RNA polymerase makes mRNA from a DNA template. There are regulatory proteins that can decrease or increase transcription. And that's important among both proarotes and ukareotes. These regulatory proteins are often referred to as transcription factors. Some transcription factors bind to a DNA region called the promoter to help RNA polymerase start transcription while other transcription factors can bind there to repress it. Some types of transcription factors can bind to enhancer sequences where they increase transcription and enhancer sequences can even be far away from the gene. Some transcription factors or other proteins can bend the DNA to bring the promoter and enhancer closer. Ultimately, transcription factors play huge roles in whether a gene is expressed. And we also want to mention environmental factors can influence transcription factors, meaning that the presence or absence of an environmental factor could impact gene expression. Proarotes commonly have operons which feature a regulated cluster of genes along with a promoter and an operator and they make great examples of gene regulation during transcription. We have an example of this in our order of the operon video, but here's a quick recap of just one type of operon known as a lac operon.

6:02 Here's a repressor. The repressor blocks RNA polymerase from doing transcription. And it does this by binding to a sequence called the operator. Since the RNA polymerase can't work, ultimately these genes are not going to get expressed. That's because the genes are not going to be transcribed into mRNA. So, it will not go to translation for a protein to be built. And that's great when the protein isn't needed. This is how the bacterium is regulating the genes in this operon. But sometimes the bacterium may need these genes expressed. And that's because these genes code for specific proteins, including an enzyme that breaks down a sugar called lactose. So when lactose is around, the bacterium wants that enzyme because it wants to break the sugar lactose down. It can eat the broken down lactose. So how does the bacterium turn a gene on? How does the gene get expressed? Well, as you can imagine, this repressor has got to be moved. It's in the way of transcription happening.

6:58 And it turns out a form of lactose, technically an isomer of it, binds to the repressor, which makes it get out of the way. When the repressor is not blocking this RNA polymerase, transcription can happen. The RNA polymerase does transcription and it makes the mRNA and translation can follow and it uses that mRNA to make protein which includes an enzyme that can break down lactose and other proteins too involved in using lactose. So these genes are being expressed when lactose is around. Expression is not happening when lactose is not around. It's a gene regulation example controlling whether genes are expressed or not. And still on the subject of gene regulation that can impact transcription, we want to mention from our epigenetics video that can impact >> we want to mention from our epigenetics video. >> There's always a massive lag in the audio stoppings, but uh that's that's enough. I mean as they alluded to there's a few other things going on and what the example they showed is basically for bacteria for for proaryotic cells where things are a bit easier uh but the general principle is often the same.

8:11 What do we make of this? A concrete example which is uh is from from the book as well why I brought it again where they tell the story nicely is uh the clock gene if you want to follow the terminology there. How how does it happen that living animals have a circadian rhythm this roughly 24 hours cycle that governs much of uh life? Now, of course, there's no uh it's not a a kind of universal constant that this is 24 hours. It's got to be the light of the sun that triggers this. But you usually wake up if you if you have regular sleep cycles, you wake up before the sun gets up roughly. And maybe even if not, then parts of your uh processes in your body start to get you ready for getting up way before the sun sets, before the sun rises. And so somehow there must be a clock started and it's by and large started in the morning with the specific um colors of light that you see in the in the sunrise. But then it kicks off a cascade of of processes that have roughly this 24-hour duration which can can then be used to trigger things at the right time before the sun gets up again. And this wouldn't work if you were just instantly reacting to light and then once the light's gone, you instantly get tired or I mean there's uh probably a lot more complicated things going on there. Uh in in animals, this seems to be more messy, but in plants um it seems there's a group of three proteins that have a ve fairly similar and consistent um function in this in this regard.

9:58 I'm not I'm not I'm not sure what these abbreviations stand for. I'm sure they have some some long chemical name. I'm just going to use use the abbreviations. There's one that uh if it's present, it means there's more translation talk one promotes the the expression of these other two. So more of them get get uh made uh with this kind of think about taking the block away as in the video. uh also sunlight seems to trigger the um their expression. But then if these two are building up over time and by the way this this protein synthesis uh depending on how big the gene is is not super fast. It might take minutes or hours to make some proteins. So this already adds a delay and if these start building up they themselves repress the expression of this other protein. So you have kind of a a feedback a negative feedback cycle so that uh over over the day um a lot of these are made they then uh repress more production of this talk one protein which triggers more pro protein production of these two. Uh but once the sunlight's gone um these start to slowly get get less. That means this talk one is no longer blocked from the high concentration of these two guys and can accumulate overnight and that kind of sets a timer for when the night is over.

11:27 If enough of talk one is there it starts promoting the production of these two again which is then enforced again by the light but also before then they start waking you up in whatever that means for a plant. I don't know that's that's roughly the story. Now the biology behind this is super exciting. Um but what this means for for our bionirmatics uh question there must be plants do a lot of things governed by this circadium cycle. All of those genes that react to the day and night cycle there must be some way how these proteins influence their expression.

12:08 And that can only really work if ahead of the genes, a bit upstream from the genes, there's a conserved pattern that these proteins can bind to to stop or promote them being expressed. So we should be able in plants to find for many genes some some similar sequences just upstream of where the gene starts. And that could I mean it could uh could be used in different ways. you can better understand how plants regulate day night. Maybe you can identify new genes and maybe you can temper with that. Um that part we were not going to get in. And these kind of conserved sequences upstream of the actual gene. These are called motives or motive in general means in this context some uh some shared common uh substring that's fairly preserved.

13:03 As always in bionformatics, don't expect the exact same string to be repeated in front of each of these genes. We'll have to live with certain little errors, mutations, and maybe also uh small changes that don't actually change the function because there might be um sort of uh equivalence classes of strings that work equally well. So the formalization that I want to look at here um in the literature is known as the consensus pattern problem. We'll I'll I'll show you an exact why that is a a natural name. Um ignore that name for the moment. Um think of it as the the motive finding problem. What we're given is a collection of strings. I call them G for genome, but really they're portions from the genome which is the region just before the gene starts. And uh let's assume from the last chapter we know how to how to identify genes. So we can know let's just read the 200 characters before the gene starts and that's our G1 to GT.

14:07 And we'll also give um a length for this motive that we expect to find. And this again from the from the proteins that people know in in plants are responsible for this. You can get some estimate. I think uh here you should think of K of being maybe 15 or a few dozen. Not not crazy large. Uh let's say or so. I mean this is a not a not a universal constant either. Uh the goal is to find in each of these genes a starting position so that if you read the next k characters from from these positions and you do this in all the different uh regions up upstream of the genes. So let me do a small picture. Maybe the region you find here lies here. Maybe here it lies here.

15:06 The positions are not really what we care about. What we care about is the content of these strings. If you write these strings on top of each other, so you should think of this being the first row here, this being the first and second row, third row and so on, then there should be a a fairly conserved pattern. And uh in formal terms, what we mean with this total Hamming distance, what we minimize here is the number of characters. So in each in each column you determine what's the most frequent character and you count the number of others. So here this column there's mostly T's. So three other letters give a contribution of three to the score to the Hamming distance. And same same for the other columns. is a bit of an un it's maybe not the most natural generalization of Hamming distance, but that's the one that seems to be most natural for the biological problem.

16:02 So if you have a a column that's not changing at all, that's constant, then it's zero and otherwise we just sum up all the columns. Is the problem clear?

16:17 Okay. Why is it called consensus pattern problem? Uh maybe you can already guess from from this example. You can rewrite a bit the definition of this Hamming distance as the sum of diff of distances in the normal Hamming distance sense from each of these uh these red subsets these substrings to uh a specific string one fixed string and that's the consensus string that you build by taking the majority vote across columns. So here uh because I I took the picture from the book, there's other things in between that only come up later. The consensus string is this one down here. It just takes the majority letter or one majority letter of each column. And then uh the total score is the Hamming distance of every row with respect to this consensus string. And of course, you're just counting the lowercase letters first by column, now by rows. If you sum this up in the end, it's the same thing, right? So the Hamming distance of the first row to the consensus would be three. These three letters and that G used to be counted here as a one. That T and that T would contribute one to these counts. But if I'm summing up column wise and then sum up those counts or summing up row-wise and then summing up those counts, that's the same.

17:44 So you could rephrase the problem here as saying we're we're looking for this consensus string, but it's it's is it's equivalent. If you know the starting positions, you know which red strings we're looking at here, then uh the consensus string can be computed from that. And so that's that's the more specific uh formulation. You get the consensus string for free. You have those starting positions.

18:10 Okay. Um, I'll come back to the other parts later. Uh, the bad news first, the problems hard and even in a in a bad way. Um, so that should be a T. Uh, it's NP hard even if the alphabet is small. They say even if it's a binary alphabet, maybe we would say uh the DNA alphabet with four letters is more natural. But that's that's uh uh not helping. And well for the complexity theory people even hoping for something that's a fixed parameter tractable algorithm in the number of strings is not going to work very likely. [snorts] Uh no proof but complexity theory assumptions aside uh we shouldn't hope to find an exact solution to this problem in good time.

19:14 Um, let's look at some simple things we could do. Brute force options to solve the problem. Exactly. Just to see how bad things get. Uh, one of one option is we're looking for these starting positions in all the strings. Remember my picture with the the red parts? I'm I'm looking for these SI, S1, S2, and so on. So that if I read K letters on each side, that has the minimum distance to a consensus string. And I could just try all combinations. How bad can you possibly get? Well, that bad. You have roughly n options in each string, n minus k. Uh, but you have to have all possible combinations. since it's not clear I a priority how to uh um separately optimize in each of the strings and so both n and t should be expected to be large in practice n is the length of the region that we're looking at that's certainly a few hundred and t is the number of genes probably also in the hundreds so that's not going to fly Um what else could we do with the reformulation of the problem from here?

20:34 Uh maybe we can first find the right consensus string and then work about worry about the rest. Uh and that indeed also works. So you could try brute force over all possible strings for the consensus string.

20:51 That brings the search space to sigma to the k still exponential but at least k is if anything that's the smallest parameter of the problem because that's the length of the region we're looking for and sigma the alphabet size is four in our case. So maybe this is uh among the bad options uh still the best. Uh what do we have to do if we guess a consensus string? We still have to find these starting positions. Uh but that turns out to be a lot more manageable because um if you're if you're given a certain consensus string and you have one of those uh GI it is independent of what the other strings choose. The best ma match between these two strings will be somewhere and you can try all the positions and just find the one that has the least Hamming distance. And the key is that you can do this independently for the different genes. So that's a bit better and overall um still exponential but uh at least no longer in all the parameters.

22:03 Um that means that this this this one here I think is for unbounded alphabets if I remember correctly. Otherwise it sounds like a contradiction to this.

22:25 Um this one indeed is somewhat practical if your motive is small. What people in practice may may do is use a smaller K, find a conserved region and see if you can grow that region manually. Um, but it's uh it's not really satisfactory like um you're likely going to miss um more important motives if if you have to make K very small.