Video 1-2: The Turnpike Problem

0:03 Let's take a step out of the lab and in this section do the mathematical formulation of the problem where um we can uh reason about what exactly that is? Now here's another this is just a fun one. Um do people still know this guy?

0:24 The problem is called [music] the turnpike problem >> and I wanted to at least show I wanted to at least show where the name comes from. Do you know what turn pike is? If you carefully seen it here was already in the right. I think it comes another time though. I'll go back briefly.

1:06 Wow. Okay. Uh, amazing series. Fun to watch. Sopranos about uh a mafia gangster having regrets. And there was the New Jersey Turnpike. Okay, I'm not going to show it again. Um, it's essentially a a tall road. Um, yeah. Uh, it's a it's a tall road. It's the American name for that. A turn pike is really the gate um that people in in medieval times had where maybe someone would charge for letting you on their road that they maintained. And for some reason it still to this day is used for ordinary highways. Uh whatever the problem comes from from this name for the roads because what we'll think about is a tall road. You can have many exits. It's a linear arrangement. It's a one-way highway. Um it's a little stupid. You can enter the highway at any of the exits. That sounds wrong. Any of the Well, they're still called exits, right? uh you can get in at any point and you get get out at any exit and essentially what you pay is proportional to the distance you traveled.

2:24 Now suppose someone just tells you uh they've driven a lot and they just give you their credit card statement with all the charges from the tall road. Can you work out what what distance was there between all the exits and in what arrangement they are on the map? That's why it's called the turnpike problem. Let me properly explain what the problem is. Uh compared to the mass spectrometry we've seen, uh we simplify a few things. First of all, uh we'll assume all the molecular weights are just integers. And we'll ignore this this nasty bit that there's these isotopes where for some things you have slightly different weights even though they're the same atom or the same element. Um, we assume every break point that you could possibly have. Remember your protein was this long uh chain of beads. Uhoh.

3:20 This long chain of beats. And you imagine you have copies broken in any every possible way. I wanted to just draw this picture from before again, but maybe uh it's good enough. You can imagine. So there's one copy where you broke it between those two and for any other possibility, you get a a peak. And we also assume if there's several ways to break the molecule into different pieces so that the sum of their molecular weights are the same, then we know this. Well, you'll see this in the spectrometry uh uh spectrum by having a larger peak, but we assume that we can exactly read off how many copies will have that peak. And we'll also assume that nobody spat into our sample and uh contaminated the whole thing. With that, um we can assume our input is a sequence of numbers. That's the beats from here. each has a different amino acid. So each has a different weight.

4:34 Okay. Um that's our input. That's what we uh in the end we want to find this. But for the moment that's that's what's given. That's the um sequence of numbers. The first thing we'll do is we'll do prefix sums. So we take the the sum of the weights from the beginning up to a certain break point. Uh that's just for for notation. So S for sums, P for protein or positions or I guess let's stick with protein but uh maybe points, I don't know, it's the distances. Um and then the key definition is the difference multis set. So that's all the numbers we can get from going from the i to the j position in our sequence and all combinations. But it's it's sub words. It's not arbitrary collections of beads. It's what we could get by breaking the molecule in in various places. Okay. [snorts] And it's a multis set because it could be that some of these numbers are the same. So a multis set essentially says you can have several copies of the same number and we know exactly how many of each.

5:50 Uh because we do that the number of these entries here is fixed. uh for every pair of position I and J I get one entry. Uh I'll have some examples for you in a sec. Um let's do the examples first. So here's uh that's the the beats have weight three five and one and two. Now you can break this up in arbitrary ways, right? So you could have just the three or the three and the five or one and two and all all these possible options. Uh formally what we defined was the prefix sums and then take differences. But you could really just work out we have the one from the one molecule that's just beat with weight one. Then we have a two because there's a beat of weight two and there's no other way to get a sum of two. But we have two copies of three because there's a beat of weight three. But also this substring of one and two sums to three. Okay. And so this is if you do this for every possible I and J uh they go from zero up to N.

7:07 Uh where here N is the length here. N would be four in this this example. Um and then you sum up uh exclusive. So k from i to j minus one pk. That's the sums that you get. And then 11 is the sum of all four. Okay. Uh here's another example. Um a simpler one. If all the weights are the same, they're all ones, then you just get all possible combinations, you get five times the one from picking each of the five individual uh elements. Then you have one, two, three, four options of getting length two by every pair and you have a few threes and two fours and a single five for the sum of all of them. >> Okay, question.

8:11 the number of bits in the first order of >> the only subwords. Yeah, that's important. That's a good point. So there's a six because we have 51, but you cannot take arbitrary subsets. Um so uh let's maybe for this small example write down all possibilities. I think it doesn't take long. So we have the three, the five, the one, the two. Then I have 3 + 5. Nobody can read this. I have five + 1. I have 1 + 2. Then I have the 3 + 5 + 1. 5 + 1 + 2. Oh god. And the sum of all and that's all. Okay. That's why this is if this what were not the case, there would be no way to get back to the sequence of numbers. you need to somehow have some information about the order, but all we've got is these weird partial sums. And then the turnpike problem is the inverse problem. We're given these uh multi- sets of differences and we're supposed to come come up with a set so that if you build this difference set difference multi- set, you come up uh come out with the input.

9:30 And so here's an example where this doesn't work. It's not always possible. First of all, the difference um difference multi set has to have a sensible number of entries. Otherwise, you're immediately out of luck. Uh but here three is fine. You get a size three difference multi set if you have two elements. So just two beats. Then we get the differences. Take take the first beat, take the second beat and take their sum. And if the difference multis set is supposed to be three times the same thing, that's not going to work, right? Then uh whatever you put a and b could be the two uh numbers and it it'll never work out to uh that distance subset. So it can't always work. Um there's a question on this. Uh, So, sequences of length one. Um, that's a nitpick of my definition. They're in there. [clears throat] Let me go. Uh, maybe it wasn't the smartest way to formalize it. It's nice and and quick to write.

10:53 Um, so here we take the difference of two prefix sums. And I'm not allowing I and J to be the same. That would give me a difference of zero. But I'm allowing J to be I + 1. And so when J is I + 1, I get essentially one of the pis.

11:19 Um, you could also have written immediately just sum of these, but then you would somehow need a notation for summing up a substring. I found this smart, but maybe it's more confusing. All all it says is what we've done in this example. You have the four letters.

11:40 Now, you can take the length one substrings, the length two substrings, the length three substrings, and so on. and always sum up their their weights.

11:55 Okay, the room fell silent. Um, that's the the right moment to have you think about a bit. This is the first non-trivial size, right? It's it's six numbers.

12:10 So, n will have to be uh I'm looking for three beats. Then I can make six combinations. Three length one substrings, two length two substrings, one length three substring. And that's it. What weights would give me this difference multis set?

12:48 We're heading for a cliffhanger lecture. I going to postpone the uh >> Yep. Uh so you have the multis set here. Um so that's that's that one.

13:48 Yeah, I think few people started figuring it out and then one submission somehow got split into three answers. I don't know if you could fix it.

14:12 Because the example is so small, you can essentially um solve this one by by trial and error almost. uh we will have to have the length one substrings somewhere in there and there's there's no way okay it's integers to make things even easier but there has to be some weight one beat in the chain otherwise we don't get this one and we have a second one so there's going to be two beats of of weight one right so there's a one and another one that's part of the ingredients. Now, this two here might be the sum of those two. So, maybe they're adjacent, but we have another two.

15:02 Probably that two is another beat. So, a guess would be that the two are adjacent and then the two is the last one. And then you can work out there's going to be a three for these two and a four for the whole thing. And that actually matches. That wasn't too bad. Maybe um and uh various people found that uh in the small case here, you can do it by trial and error, but it's kind of hard, right? Yeah.

15:45 Yeah. The whole problem is um is oblivious to reversing the word. So the best we can possibly hope for is identifying the sequence or its reverse. We cannot distinguish those two. Yep, that's a very good point.