東京大学 新領域創成科学研究科 メディカル情報生命専攻 2017年8月実施 問題12

标签：

• 东京大学
• 最长公共子序列

Author

zephyr, 祭音Myyura

Description

For two strings $\mathbf{x} = x[1] \cdots x[n]$ and $\mathbf{y} = y[1] \cdots y[m]$ of lengths $n$ and $m$ ($n \geq 0, m \geq 0$), we define the set of common subsequences as

$$S = \left\{ \begin{pmatrix} i_1, \cdots, i_r \\ j_1, \cdots, j_r \end{pmatrix} \mid r: \text{positive integer}, \begin{matrix} 1 \leq i_1 < \cdots < i_r \leq n \\ 1 \leq j_1 < \cdots < j_r \leq m \end{matrix}, x[i_k] = y[j_k], k = 1, \cdots, r \right\}$$

Here, $r$ represents the length of common subsequence $\begin{pmatrix} i_1, \cdots, i_r \\ j_1, \cdots, j_r \end{pmatrix}$. Let $l(x, y)$ denote the length of the longest common subsequences. If $S = \emptyset$, we define $l(x, y) = 0$.

(1) Let $z_k^p$ and $z_k^s$ denote the length-$k$ prefix and suffix of string $z$, respectively. We define $\alpha[i, j] = l(x_i^p, y_j^p)$ and $\beta[i, j] = l(x_{n-i+1}^s, y_{m-j+1}^s)$ for $1 \leq i \leq n, 1 \leq j \leq m$. Describe a recurrence for computing $\alpha[i, j]$ from $\alpha[i-1, j-1]$, $\alpha[i-1, j]$, and $\alpha[i, j-1]$ when $1 < i, 1 < j$. Also, describe a recurrence for computing $\beta[i, j]$ from $\beta[i+1, j]$, $\beta[i, j+1]$, and $\beta[i+1, j+1]$ when $i < n, j < m$.

(2) Compute matrices $\alpha$ and $\beta$ for $\mathbf{x} = \text{ACTGG}$ and $\mathbf{y} = \text{ACACG}$.

(3) Suppose matrix $\alpha$ is given. Write a pseudocode for obtaining one of the longest common subsequences.

(4) Suppose matrices $\alpha$ and $\beta$ are given. Write a pseudocode for computing the maximal length of common subsequences that contain the $i$-th position of $\mathbf{x}$ ($1 \leq i \leq n$).

---

对于长度为 $n$ 和 $m$ 的两个字符串 $\mathbf{x} = x[1] \cdots x[n]$ 和 $\mathbf{y} = y[1] \cdots y[m]$ ($n \geq 0, m \geq 0$)，我们定义公共子序列集为

$$S = \left\{ \begin{pmatrix} i_1, \cdots, i_r \\ j_1, \cdots, j_r \end{pmatrix} \mid r: \text{正整数}, \begin{matrix} 1 \leq i_1 < \cdots < i_r \leq n \\ 1 \leq j_1 < \cdots < j_r \leq m \end{matrix}, x[i_k] = y[j_k], k = 1, \cdots, r \right\}$$

这里，$r$ 表示公共子序列 $\begin{pmatrix} i_1, \cdots, i_r \\ j_1, \cdots, j_r \end{pmatrix}$ 的长度。令 $l(x, y)$ 表示最长公共子序列的长度。如果 $S = \emptyset$，我们定义 $l(x, y) = 0$。

(1) 令 $z_k^p$ 和 $z_k^s$ 分别表示字符串 $z$ 的长度为 $k$ 的前缀和后缀。我们定义 $\alpha[i, j] = l(x_i^p, y_j^p)$ 和 $\beta[i, j] = l(x_{n-i+1}^s, y_{m-j+1}^s)$ 对于 $1 \leq i \leq n, 1 \leq j \leq m$。描述从 $\alpha[i-1, j-1]$，$\alpha[i-1, j]$，和 $\alpha[i, j-1]$ 计算 $\alpha[i, j]$ 的递推关系，当 $1 < i, 1 < j$。同时，描述从 $\beta[i+1, j]$，$\beta[i, j+1]$，和 $\beta[i+1, j+1]$ 计算 $\beta[i, j]$ 的递推关系，当 $i < n, j < m$。

(2) 计算 $\mathbf{x} = \text{ACTGG}$ 和 $\mathbf{y} = \text{ACACG}$ 的矩阵 $\alpha$ 和 $\beta$。

(3) 假设给定矩阵 $\alpha$。编写伪代码以获取一个最长的公共子序列。

(4) 假设给定矩阵 $\alpha$ 和 $\beta$。编写伪代码以计算包含 $\mathbf{x}$ 的第 $i$ 个位置的最大长度的公共子序列 ($1 \leq i \leq n$)。

题目描述

给定长度分别为 $n,m$（$n,m\ge0$）的字符串

$$\mathbf x=x[1]\cdots x[n],\qquad \mathbf y=y[1]\cdots y[m].$$

公共子序列用两列严格递增的下标

$$\begin{pmatrix}i_1,\ldots,i_r\\j_1,\ldots,j_r\end{pmatrix}$$

表示，其中 $r$ 为正整数，

$$1\le i_1<\cdots<i_r\le n,\qquad 1\le j_1<\cdots<j_r\le m,$$

且对每个 $k=1,\ldots,r$ 都有 $x[i_k]=y[j_k]$。最长公共子序列长度记为 $l(x,y)$；若不存在公共子序列，则定义 $l(x,y)=0$。

1. 令 $z_k^p,z_k^s$ 分别为字符串 $z$ 的长度 $k$ 前缀和后缀，并定义

   $$\alpha[i,j]=l(x_i^p,y_j^p),\qquad \beta[i,j]=l(x_{n-i+1}^s,y_{m-j+1}^s).$$

   对 $1<i,1<j$，给出由 $\alpha[i-1,j-1]$、$\alpha[i-1,j]$、$\alpha[i,j-1]$ 计算 $\alpha[i,j]$ 的递推；对 $i<n,j<m$，给出由 $\beta[i+1,j]$、$\beta[i,j+1]$、$\beta[i+1,j+1]$ 计算 $\beta[i,j]$ 的递推。

2. 对 $\mathbf x=\mathrm{ACTGG}$、$\mathbf y=\mathrm{ACACG}$，计算完整矩阵 $\alpha,\beta$。

3. 已知 $\alpha$，编写取得一个最长公共子序列的伪代码。

4. 已知 $\alpha,\beta$，编写伪代码，对指定 $1\le i\le n$ 求所有包含 $\mathbf x$ 第 $i$ 个位置的公共子序列中的最大长度。

Kai

(1)

Recurrence for $\alpha[i, j]$

The value of $\alpha[i, j] = l(x_i^p, y_j^p)$ can be computed as follows:

• If $x[i] = y[j]$, then $\alpha[i, j] = \alpha[i-1, j-1] + 1$.
• If $x[i] \neq y[j]$, then $\alpha[i, j] = \max(\alpha[i-1, j], \alpha[i, j-1])$.

This can be summarized as:

$$\alpha[i, j] = \begin{cases} \alpha[i-1, j-1] + 1 & \text{if } x[i] = y[j] \\ \max(\alpha[i-1, j], \alpha[i, j-1]) & \text{if } x[i] \neq y[j] \end{cases}$$

Use the boundary values $\alpha[0,j]=\alpha[i,0]=0$.

Recurrence for $\beta[i, j]$

The value of $\beta[i, j] = l(x_{n-i+1}^s, y_{m-j+1}^s)$ can be computed as follows:

• If $x[i] = y[j]$, then $\beta[i, j] = \beta[i+1, j+1] + 1$.
• If $x[i] \neq y[j]$, then $\beta[i, j] = \max(\beta[i+1, j], \beta[i, j+1])$.

This can be summarized as:

$$\beta[i, j] = \begin{cases} \beta[i+1, j+1] + 1 & \text{if } x[i] = y[j] \\ \max(\beta[i+1, j], \beta[i, j+1]) & \text{if } x[i] \neq y[j] \end{cases}$$

Use the boundary values $\beta[n+1,j]=\beta[i,m+1]=0$.

(2)

Matrix $\alpha$

Let's fill the matrix $\alpha$ for $\mathbf{x} = \text{ACTGG}$ and $\mathbf{y} = \text{ACACG}$:

x\y	A	C	A	C	G
A	1	1	1	1	1
C	1	2	2	2	2
T	1	2	2	2	2
G	1	2	2	2	3
G	1	2	2	2	3

Matrix $\beta$

Let's fill the matrix $\beta$ for $\mathbf{x} = \text{ACTGG}$ and $\mathbf{y} = \text{ACACG}$. The row and column indices are displayed in descending order:

x\y	G	C	A	C	A
G	1	1	1	1	1
G	1	1	1	1	1
T	1	1	1	1	1
C	1	2	2	2	2
A	1	2	3	3	3

(3)

To extract one of the longest common subsequences from the matrix $\alpha$, we use the following algorithm. This algorithm traces back from the bottom-right corner of the matrix to the top-left corner, reconstructing the longest common subsequence by following the path of optimal choices recorded in $\alpha$.

Explanation

• Start from the bottom-right corner of the matrix $\alpha$, i.e., $\alpha[n, m]$.
• Compare characters of $\mathbf{x}$ and $\mathbf{y}$:
  • If $x[i] = y[j]$, include $x[i]$ in the result and move diagonally to $\alpha[i-1, j-1]$.
  • If $x[i] \neq y[j]$, move in the direction that gives the larger value (either up or left).
• Continue until one of the remaining prefixes is empty.
• The resulting list of matched index pairs represents one of the longest common subsequences; their characters can be read from $x$.

Pseudocode

function getLCS(x, y, alpha)
    i = length(x)
    j = length(y)
    pairs = []
    while i > 0 and j > 0
        if x[i] == y[j]
            append (i, j) to pairs
            i = i - 1
            j = j - 1
        else if alpha[i-1, j] >= alpha[i, j-1]
            i = i - 1
        else
            j = j - 1
    reverse pairs
    return pairs

(4)

Given matrices $\alpha$ and $\beta$, match $x[i]$ with some equal character $y[j]$. Combine a common subsequence before these positions, this matched pair, and a common subsequence after them.

Explanation

• For each position $j$ in $\mathbf{y}$:
  • If $x[i]=y[j]$, the maximal length using this pair is $\alpha[i-1,j-1]+1+\beta[i+1,j+1]$.
• The maximum value obtained through this process gives the desired length.

Pseudocode

function maxLengthWithPosition(x, y, alpha, beta, i)
    maxLength = 0
    for j = 1 to length(y)
        if x[i] == y[j]
            currentLength = alpha[i-1, j-1] + 1 + beta[i+1, j+1]
            maxLength = max(maxLength, currentLength)
    return maxLength

If no character of $y$ matches $x[i]$, there is no common subsequence containing this position; the function returns $0$ in that case.

Knowledge

动态规划 最长公共子序列 递归

难点思路

对于递归关系的理解和矩阵填充的具体实现可能会比较复杂，需要仔细考虑每一步的递推关系。

解题技巧和信息

• 动态规划表格填充方法：先初始化，然后按照递推关系逐步填充。
• 递归关系需要对字符串字符的匹配情况进行详细考虑，以确保递推关系的正确性。

重点词汇

• common subsequence 公共子序列
• recurrence relation 递推关系
• prefix 前缀
• suffix 后缀
• dynamic programming 动态规划

参考资料

1. Introduction to Algorithms, 3rd Edition, Cormen et al., Chapter 15.

Reference

• 東京大学 CBMS 公式過去問