The Manhattan Tourist Problem

The Manhattan Tourist Problem


[MUSIC] And we now move to the next topic that,
once again, seemingly has nothing to do with
the sequence comparison. We are now on a sightseeing tour in
Manhattan. And our goal is to walk from the
intersection shown in blue to the intersection shown in red.
And to visit as many attractions as possible. The only restriction is that we can either
move south or east. What should be our strategy to visit the maximum number of attractions on this
trip? We can model Manhattan as a grid, and show
edges in this grid where there are attractions as edges of rate one, and then
our goal is to find a path in this graph that has maximum number of
attractions. Sometimes computer scientists call this a longest path in this graph from the
blue node to the red node. We can actually try to solve this problem
in an arbitrary grid with this arbitrary number of
attractions, like this grid shown here. There are many different ways to travel in
this grid. For example, we can travel like this, and in this case, we’ll
visit 18 attractions. The length of the longest path is 18. Is it an optimal path?
No, because we can travel differently, and in this case, visit 20 attractions.
What should be our strategy, for the optimum exploration of Manhattan.
We need to solve the Manhattan tourist problem. The input is a weighted rectangular grid,
and the output is a longest path from the source
vertex (node), the vertex shown by blue, to the sink
vertex (node) that is shown by red in this grid. So what should we do? The simplest thing that comes to mind is
to explore a greedy strategy. For example, being in the very beginning,
we can either move east or move south. If you move east, we will visit three
attractions immediately. If we move south, we will visit only one. It makes sense to move east.
Let’s do it. Then, afterwards, once again, we can move
either east or south. We make choice based on the more, maximum
number of attractions. And we continue like this, and finally, we arrive to the source, visiting 23
attractions. And you have already guessed that this is a very simple
strategy. But not an optimal one. We need now to find the optimal strategy. Another thing we need to keep in mind is that Manhattan is not a perfect
rectangular grid. Broadway cuts across. And we can model this grid as an arbitrary
graph where edges can go from whatever vertex (node)
to whatever node. And how do we travel in this grid? And to travel in this grid, we need to
solve (find) the longest path in a directed graph problem,
where the input is an edge-weighted directed graph with the source
and sink nodes, and the output is simply a longest path from source to sink
in this graph. Now you may be surprised by now why I’m talking about alignment game and
Manhattan. Do you see a connection between the longest path problem and the
alignment game? And it may be not obvious that there is a connection but let’s try to figure out
what is it. For every column of the alignment
matrix, let’s code it with an arrow, as I showed in the slide. And then, after we design this arrow, let’s see how
this arrow would translate into the new grid that I have constructed
and presented in this slide. The first arrow is diagonal. Let’s move diagonally in our grid. The next arrow is also diagonal, let’s
move diagonally again. The next arrow is horizontal. We continue further horizontally. Diagonal, diagonal, vertical, diagonal,
vertical, diagonal, and actually using alignment matrix, we
were able to travel in the Manhattan grid. Right? Now, let’s ask a reverse question. If we have a path in Manhattan grid, would we be able to construct the
alignment matrix? Let’s try. This is an arbitrary path in the alignment grid.
Let’s combine all the arrows in one place. And as soon as we’ve done it, of course we can construct the alignment matrix as I
showed here. Therefore, alignments are nothing but
passes in the grid. And therefore, to play the alignment game, to construct longest common subsequences,
the only thing we need to do is to travel
optimal ways in the graph. And the often question for sequence
comparison problem in biology amounts to build an
appropriate Manhattan. We’ll do it a lot in this lecture. In the case of the longest common subsequence,
what would be this Manhattan? In this case, diagonal red edges
correspond to matching symbol and have a score of one. If these corresponding symbols for these
diagonal edges match to each other.
And highest scoring alignment in this case is simply the longest path in a
properly built Manhattan. And to learn how we travel in whatever
Manhattan, we need once again to talk about the
problem that seemingly has nothing to do with biology.
And it is the change problem.

Leave a Reply

Your email address will not be published. Required fields are marked *