Sightseeing in an Arbitrary Directed Graph
Explore how to identify the longest path in edge-weighted directed acyclic graphs, which is essential for modeling and comparing biological sequences. Understand the problem setup, its relation to genome analysis, and how it connects to sequence alignment techniques. This lesson helps you grasp a fundamental graph algorithm used in bioinformatics data analysis.
We'll cover the following...
In reality, the streets in Midtown Manhattan don’t form a perfect rectangular grid because Broadway Avenue cuts diagonally across the grid, but the network of streets can still be represented by a directed graph. In fact, the Manhattan Tourist Problem is just a special case of the more general problem of finding the longest path in an arbitrary directed graph, such as the ones in figure below.