CBMS-2015-12

题目来源：Question 12 日期：2024-08-01 题目主题：CS-算法-动态规划-序列比对

解题思路

这道题目主要涉及序列比对中的动态规划算法，特别是关于全局比对和空位罚分的计算。我们需要：

1. 分析给定的递推公式，推导出空位罚分函数的一般形式
2. 根据给定的初始条件，确定边界情况的初始值
3. 解释生物序列比对中常用的参数设置
4. 分析更复杂的空位罚分模型，并推导其一般形式

关键是要理解动态规划算法在序列比对中的应用，以及不同空位罚分模型的意义和影响。

Solution

1. General form of the gap score $g(k)$

To find the general form of $g(k)$, we need to analyze the recursive formulas for $X(i,j)$ and $Y(i,j)$.

For a gap of length $k$, the score will be:

$$g(k)=-d-(k-1)e$$

Explanation:

• The first gap opening costs $d$
• Each subsequent gap extension costs $e$
• For a gap of length $k$, we have 1 opening and $k-1$ extensions

Therefore, the general form of $g(k)$ is:

$$g(k)=-d-(k-1)e$$

2. Initial values for $X(i,0)$ and $Y(0,j)$

Given the initial conditions:

$$\begin{array}{rl}M(0,0)& =0,\\ X(0,0)& =Y(0,0)=-\infty ,\\ M(i,0)& =Y(i,0)=-\infty (i=1,\dots ,m),\\ M(0,j)& =X(0,j)=-\infty (j=1,\dots ,n).\end{array}$$

We need to determine $X(i,0)$ for $i=1,\dots ,m$ and $Y(0,j)$ for $j=1,\dots ,n$.

For $X(i,0)$:

$$\begin{array}{rl}X(1,0)& =\max [M(0,0)-d,X(0,0)-e]=\max [-d,-\infty ]=-d\\ X(2,0)& =\max [M(1,0)-d,X(1,0)-e]=\max [-\infty ,-d-e]=-d-e\\ X(3,0)& =\max [M(2,0)-d,X(2,0)-e]=\max [-\infty ,-d-2e]=-d-2e\\ & ⋮\end{array}$$

Therefore, $X(i,0)=-d-(i-1)e$ for $i=1,\dots ,m$.

For $Y(0,j)$:

$$\begin{array}{rl}Y(0,1)& =\max [M(0,0)-d,Y(0,0)-e]=\max [-d,-\infty ]=-d\\ Y(0,2)& =\max [M(0,1)-d,Y(0,1)-e]=\max [-\infty ,-d-e]=-d-e\\ Y(0,3)& =\max [M(0,2)-d,Y(0,2)-e]=\max [-\infty ,-d-2e]=-d-2e\\ & ⋮\end{array}$$

Therefore, $Y(0,j)=-d-(j-1)e$ for $j=1,\dots ,n$.

3. Reason for setting $d>e$ in biological sequence alignment

In biological sequence alignment, we usually set $d>e$ (i.e., the gap opening penalty is larger than the gap extension penalty) for the following reasons:

1. Biological relevance: In evolutionary processes, it’s more likely for a single mutation event to cause a contiguous gap (insertion or deletion) of multiple residues than for multiple independent single-residue indel events to occur adjacently. Setting $d>e$ reflects this biological reality.

2. Alignment quality: This setting encourages fewer, longer gaps rather than many short gaps in the alignment. This often leads to more biologically meaningful alignments, as it better represents the evolutionary events that may have occurred.

3. Computational efficiency: By discouraging the introduction of many small gaps, this setting can reduce the search space for optimal alignments, potentially improving the efficiency of alignment algorithms.

4. General form of gap score for the more complex model

For the more complex model with two sets of gap penalties $(d_1,e_1)$ and $(d_2,e_2)$, where $d_2>d_1$ and $e_2>e_1$, the general form of the gap score $g(k)$ will be:

$$g(k)=\{\begin{array}{ll}-d_1-(k-1)e_1& \text{if }1\le k\le k^{\ast }\\ -d_2-(k-1)e_2& \text{if }k>k^{\ast }\end{array}$$

where $k^{\ast }$ is the break-even point where the two scoring schemes give the same result.

To find $k^{\ast }$, we solve:

$$-d_1-(k^{\ast }-1)e_1=-d_2-(k^{\ast }-1)e_2$$

Solving for $k^{\ast }$:

$$k^{\ast }=\frac{d_2-d_1}{e_2-e_1}+1$$

Note that $k^{\ast }$ may not be an integer. In practice, we would use the floor or ceiling of this value, depending on the specific requirements of the alignment algorithm.

This more complex model allows for a more nuanced treatment of gap penalties, potentially leading to more accurate alignments, especially for sequences with varying gap length distributions.

知识点

动态规划序列比对全局比对生物信息学

难点思路

1. 理解动态规划在序列比对中的应用
2. 分析递推公式以推导空位罚分函数
3. 理解不同空位罚分模型的生物学意义
4. 处理更复杂的空位罚分模型，并推导其一般形式

解题技巧和信息

1. 分析递推公式时，关注 gap opening 和 gap extension 的区别
2. 初始值的设置对于动态规划算法的正确性至关重要
3. 在生物序列比对中，参数的设置常常基于生物学知识和经验
4. 处理分段函数时，寻找分界点（break-even point）是关键

重点词汇

• Global alignment: 全局比对
• Dynamic programming: 动态规划
• Gap penalty: 空位罚分
• Gap opening penalty: 空位开放罚分
• Gap extension penalty: 空位延伸罚分
• Sequence alignment: 序列比对
• Affine gap penalty: 仿射空位罚分

参考资料

1. Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Chap. 3.