1.1. 曼哈顿游览问题¶
我们将通过一个非常实用的玩具问题，即曼哈顿游览者问题，进一步说明动态规划，然后利用这一直觉来描述 DNA 序列比对。游览者必须在西北最远点 （称为源顶点） 和东南最远点 （称为汇点） 之间做出众多可能的路径选择。从源点到汇点的路径权重 简单地就是其边权重的总和，或者整体吸引力的数量 。我们将将这种构造称为 图 ，我们将街道的交叉点称为顶点，街道本身将作为边，并与它们相关联的权重。我们假设图中的水平边朝 向东，箭头指向 ，而垂直边朝 向南，箭头指向 。 路径 是一个连续的边序列，路径的长度是路径中边权重的总和。 曼哈顿游览者问题 是找到最多吸引力的路径，即在网格中最长的路径（最长的整体权重路径）。 曼哈顿游览者问题 ：在加权网格中找到最长的路径。 输入：一个加权网格 G，有两个特殊的顶点：源点和汇点。 输出：从源点到汇点的最长路径。
1.1.1. 在矩形城市网格中使用贪心算法找到最长路径¶
暴力破解 方法是搜索网格中的所有路径，找到最长的路径，但即使对于中等规模的网格，这也是一个不切实际的选择。根据上一章的启发，你可能会被贪婪策略所诱惑。例如，一个合理的贪婪策略是 在两个可能的方向（南或东）之间做出选择 ，通过比较游客在向南移动一格而不是向东移动一格时会看到多少景点。这种贪婪策略在开始阶段可能会提供令人满意的观光体验，但几英里后，你可能会到达一个你根本不想去的曼哈顿区域。事实上，目前已知的贪婪策略对于曼哈顿游览问题来说，没有提供最优解。如果我们遵循了（显而易见的）贪婪算法，我们将会选择以下路径，对应着四十二个景点。
1.1.2. 在矩形城市网格中使用动态规划找到最长路径¶
相比直接解决曼哈顿游览问题，即从源点（0,0）到汇点（n,m）找到最长路径，我们解决一个更通用的问题：从源点到任意顶点（i,j），其中0 ≤ i ≤ n, 0 ≤ j ≤ m。我们将此最优路径的长度记为 si,j，注意到 sn,m 是代表曼哈顿游览问题的解决方案路径的权重。如果我们只关心从（0,0）到（n,m）之间的最长路径——曼哈顿游览问题——那么我们需要回答一个问题，即从源点到汇点如何到达。如果我们解决这个通用的问题，那么我们需要回答 n × m 个问题：从源点到任意位置如何到达。乍一看，我们似乎刚刚创建了 n × m 个不同的问题（计算（i, j），其中 0 ≤ i ≤ n, 0 ≤ j ≤ m），而不是一个（计算 sn,m）的单一问题，但解决这个更通用的问题之所以容易，是因为动态规划的基础。需要注意的是，DPCHANGE 还通过找到所有值小于或等于 M 的最优硬币数来推广了它所解决的问题。找到 s0,j（对于 0 ≤ j ≤ m）并不难，因为在这种情况下，游客在路径选择上没有灵活性。通过严格向东移动，s0,j 的路径权重是前 j 个城市区的权重的总和。同样，对于 0 ≤ i ≤ n，si,0 也是容易计算的，因为游客只向南移动。
现在我们已经弄清楚了如何计算 s0,1 和 s1,0，我们可以计算 s1,1。 游客只能通过两种方式到达 (1, 1)：要么从 (0, 1) 向南移动，要么从 (1, 0) 向东移动。 这些路径的权重分别为
s0,1 + (0,1) 和 (1,1) 之间的边（块）的权重
s1,0 + (1,0) 和 (1,1) 之间的边（块）的权重。
- 由于目标是找到从 (1, 1) 到这里的最长路径，因此我们选择上述两个量中的较大者：
3 + 0 和 1 + 3。注意，由于没有其他到达网格位置 (1, 1) 的方式，
我们已经找到了从 (0, 0) 到 (1, 1) 的最长路径。计算好 s1,1 之后，我们可以使用相同的思路计算 s1,2 对于所有 i，依此类推。例如，我们可以计算 s1,2 如下。s1,2 = max(s1,1 + (1,1) 和 (1,1) 和 (1,2) 之间的边（块）的权重，s0,2 + (0,2) 和 (1,2) 之间的边（块）的权重）
1.1.3. 从曼哈顿到对齐图¶
我们对“DNA序列之间的相似度”或“距离”一词的定义一直很模糊。在计算机科学中，哈明距离虽然很重要，但通常不用于比较DNA或蛋白质序列。 哈明距离的计算 严格地假设了两个序列中第i个符号是否已经对齐。然而，一个序列中第i个符号通常对应于另一个序列中一个不同且未知的位。例如， DNA中的突变是进化过程： DNA复制错误会导致核苷酸的替换、插入和删除，导致“编辑后的”DNA文本。由于DNA序列容易发生 插入和删除 ，生物学家很少能预先知道一个DNA序列中第i个符号是否对应于另一个序列中的第i个符号。1966年，弗拉基米尔·列文施坦引入了两个字符串之间的编辑距离的概念 ，即在不超过两个编辑操作 （其中编辑操作包括插入一个符号、删除一个符号和将一个符号替换为另一个符号）后将一个字符串转换为另一个字符串所需的最小次数。
1.1.3.1. 从对齐到路径¶
两行中包含相同字母的字符串称为 匹配，而包含不同字母的字符串称为 错配。比对中包含一个空格的字符串称为 indels，其中顶行包含空格的列称为 插入，底行包含空格的列称为 删除。比对节点中的每个字符串都表示为从网格中的 (0, 0) 到 (n, m) 由空格符号"−"间隔的字符串。此网格类似于我们之前介绍的曼哈顿网格，其中网格中的每个条目看起来像一个城市街区。主要区别在于这里我们可以沿对角线移动。我们可以通过为网格中每条街道的每个交叉口引入一个顶点来构建一个图，这次称为编辑图，如可视化所示。编辑图将帮助我们计算编辑距离。每个比对对应于编辑图中的一条路径，编辑图中的每条路径对应于一个比对，其中路径中的每条边对应于比对中的一列。路径中以图中顶点 (i, j) 结束的对角边对应于列，水平边和垂直边
分析对齐的优劣与分析对应路径的优劣相同。对于任意两个字符串，在编辑图中存在大量的不同对齐矩阵和对应路径。其中一些具有过多的错配和插入/缺失以及少量匹配，而另一些则具有许多匹配和少量插入/缺失和错配。为了确定一个对齐相对于另一个的相对优劣，我们依赖于评分函数的概念，该函数将对齐矩阵（或等效地编辑图中的路径）作为输入，并产生一个分数，该分数确定了对齐的“优劣”。我们可以使用各种评分函数，但我们希望有一个能够为具有更多匹配的对齐评分更高的函数。
1.1.3.2. 从路径到对齐¶
最简单的序列相似度分析形式是最长公共子序列（LCS）问题，其中我们消除了替换操作，只允许插入和删除。一个字符串的子序列是从字符串 v 中的（不一定连续）字符序列。例如，如果 v = ATTGCTA，则 AGCA 和 ATTA 是 v 的子序列，而 TGTT 和 TCG 则不是。9 两个字符串的共同子序列是从它们中的一种子序列。形式上，我们定义了字符串 v = v1 . . . vn 和 w = w1 . . . wm 的共同子序列为一个在 v 中的位序列，1 ≤ i1 < i2 < · · · < ik ≤ n 和一个在 w 中的位序列，1 ≤ j1 < j2 < · · · < jk ≤ m，使得在 v 和 w 中的相应位置的符号一致：vjt = wjt，对于 1 ≤ t ≤ k。例如，TCTA 是两个字符串 ATCTGAT 和 TGCATA 的共同子序列。尽管通常两个字符串 v 和 w 之间有许多共同子序列，其中一些比另一些更长，但如何找到最长的一个并不直观。如果我们令 s(v, w) 为 v 和 w 最长公共子序列的长度，则在假设只允许插入和删除的情况下，编辑距离 d(v, w) = n + m - 2s(v, w)，对应于将 v 转换为 w 所需的最小插入和删除次数。
最长公共子序列问题
- 找到两个字符串的最长子序列公共部分。
输入：两个字符串，v 和 w。
输出：v 和 w 的最长公共子序列
