The Manhattan Tourist Problem

A revolution is coming. Recent advances in genetics are heralding a new era in which dangerous and life-threatening hereditary disorders such as Sickle Cell Anemia may be nothing but a thing of the past.

However, the underpinnings of this revolution lie in bioinformatics algorithms that developed decades before the Human Genome Project. The Manhattan Tourist Problem is one such algorithm, being the foundation of algorithms that solve genome assembly (piecing together fragmented DNA sequences) and comparison (finding similarities and differences between genomes).

To learn more about this algorithm, see our recent video below. Alternatively, you can read the video transcript (slightly modified to include links) further in this blog.

Transcript

Start

Imagine you're a tourist trying to see as much as possible in Manhattan—what's the best route? 

This is known as the Manhattan Tourist Problem, and it turns out it can help us solve core challenges in bioinformatics, like comparing DNA and protein sequences.

The Problem

To start, let’s define our problem by imagining that we have a city such as Manhattan.

We can represent Manhattan as a grid of intersecting streets, with attractions scattered along the streets. 

Now, if I start in the top-left corner, at the intersection of 59th Street and 8th Avenue, and want to end up at the bottom-right corner, at the intersection of 42nd Street and 4th Avenue, how can I maximize the number of attractions I visit?

We can only move down or to the right―that way we’re always progressing towards our destination and not going backwards.

Approaching the Problem

To simplify this, we’ll treat attractions as “weights” on the edges of our grid. Every time we pass an edge, we add its weight—the number of attractions next to it—to our total score.

This turns our city into a weighted, directed graph where each edge points either down or right.

We can now redefine our problem. Our problem is to make a path through a weighted grid and maximize the sum of the weights along the path.

Let’s start from the top-left corner and see how we can make the best choices along the way to reach the bottom-right corner with the highest score.

In our first step, it doesn’t matter if we go right or if we go down. Either way, we don’t encounter anything. We can give both of these nodes a score of 0. Let’s just look at what happens if we go down.

Once again, if we go right or go down, it doesn’t matter since there aren’t any edges. So we can fill in some more zeros. If we look at what happens when we go right, however, we finally run into an interesting choice. If we go to the right again, then we have an edge with weight 1, so we’ll increment our score by 1. If we go down, we have an edge with weight 0 and we won’t increment the value.

If we follow the example path on screen, we end up taking a path with a score of 6. There are plenty of different paths we can take that will lead to paths with different scores.

At each point in the grid, we want to have taken the path that gives us the highest total score. So for every node, we look at the two possible paths leading into it—from above or from the left—and take the one that gives us the highest total. Let’s use this approach to begin populating the grid.

Solving the Problem

The top left corner will have a score of zero. Neither of the edges next to it have a nonzero weight, so the adjacent coordinates will just be zero.

Now, let’s look at the point at the intersection of 57th Street and 7th Avenue. Since there are no weighted edges going into the point, and both the point above and to the left of it are zero, then this point’s score is still zero. The scores of the intersections of 55th Street and 8th Avenue as well as 59th Street and 6th Avenue are also 0 by similar logic.

If we now try and fill in the point at the intersection of 57th Street and 6th Avenue, however, we see something interesting. Above it we have a zero, and there is no weight along the edge. To its left is a point that’s also a zero, but the edge between the points has a weight of 1. This means that it has an attraction along that edge. If we were to take the path from the node above to get to this point, then we would still be at 0. However, if we were to take the path from the node to the left to get to this point, then we would add the weight to get a score of 1. Therefore, we would want to take the path from the left. At this point, the maximum score we could have is 1.

The score at any point equals the maximum of two values: the score from above plus the edge weight from above, and the score from the left plus the edge weight from the left.

By applying this rule across the entire grid, we build up the best possible path at every point. And in the end, the score in the bottom right corner tells us exactly what we want to know: the maximum number of attractions we can visit on our journey from start to finish.

Conclusion

Now that we’ve broken down the problem, I challenge you all to write out the solution in code yourself. If you have any questions, feel free to leave a comment. I have written an example solution in Go that can be found at https://gist.github.com/aaguy-hue/2a0b79fa780677de6b10f4dfea52c617.

While the problem might just seem like little more than a fun puzzle, it actually mirrors the same logic we use in genome alignment—an algorithm used for applications including comparing DNA sequences and assembling sequenced fragments of genomes.

If a video on alignment sounds like something that you would be interested in, please subscribe. Also, if you liked the video, please leave a like, and if you disliked it, then press the dislike button and leave a comment explaining what I could do better.

Before I end this video, I want to thank Dr. Phillip Compeau and Dr. Josh Kangas for teaching the Pre-College Program in Computational Biology at Carnegie Mellon University and sparking my interest in bioinformatics. Also, massive thanks to Grant Sanderson from 3Blue1Brown for his videos that inspired me to make my own.

Thank you all for watching, and I hope you all have a great day.