双序列比对 Pairwise sequence alignment ——序列比对Sequence Alignment.

type

status

date

slug

summary

📝 成对序列比对问题

目标：根据定义的评分系统对两个生物序列进行最佳比对，以最大化它们的相似性。

为了解决成对序列比对问题，首先考虑一个基本问题——最长公共子序列问题，简称LCS问题。

最长公共子序列问题(LCS)

问题说明

给定两个字符串 X 和 Y，目标是找出它们最长公共子序列的长度。

举个例子：

•序列1：ABCBDAB

•序列2：BDCABA

最长公共子序列是 BDAB，因为 BDAB 这个序列在两个字符串中都出现了，而且顺序不变。

LCS问题的基本想法

现在我们有两个字符串，我们想要找出它们的最长公共子序列。如果我们能比较出每个字符的匹配情况，那么就可以逐步构造出这个子序列。

问题分解：

假设我们已经处理完了两个序列的前几个字符，接下来要比对剩余的部分。如果两个序列的最后一个字符相同，那么我们可以直接把它们加到子序列里；如果它们不同，则我们需要分别考虑去掉其中一个字符的情况，看哪种选择能得到更长的子序列。

动态规划解决LCS问题

要解决LCS问题，我们可以使用动态规划的技巧。

动态规划是一种把大问题分解为小问题，逐步解决的策略。我们可以通过一个二维表（矩阵）来存储每对字符的最长公共子序列长度，然后通过这个表来构造最终的LCS。

动态规划的具体步骤：

1.创建一个二维表：行表示序列1的每个字符，列表示序列2的每个字符。

2.填充这个表：根据序列中的字符是否相同来填充表格。我们会逐步构造出每个前缀的LCS长度。

3.回溯找出最终的LCS：从表格的最后一个格子（表示整个序列）往前追溯，构造最长公共子序列。

具体代码实现

解释：

1.findLCS函数：

•这个递归函数从二维数组 dp 中回溯，构造所有可能的最长公共子序列。

•如果遇到两个字符相同，直接将其加入当前的LCS并继续向左上角（i-1, j-1）回溯。

•如果两个字符不同，则分别沿着 dp[i-1][j] 和 dp[i][j-1] 的方向回溯，这样可以探索多个可能的路径。

2.LCS函数：

•首先使用动态规划计算出 dp 表格。

•然后通过 findLCS 递归函数回溯并找到所有的最长公共子序列，将结果存储在一个 set<string> 中。set 自动去除重复的子序列。

全局序列对比问题

Pairwise sequence alignment（成对序列比对）和LCS（最长公共子序列）有着紧密的联系。LCS可以看作是Pairwise sequence alignment中的一个特例。在Pairwise sequence alignment中，我们不仅仅关心两个序列中公共子序列的长度，还会考虑序列中的“错配”（mismatch）和“插入/缺失”（gap）情况，并通过一定的“打分体系”来找到最佳的比对方式。

全局序列比对旨在对整个序列进行比对，通常用于长度相似的序列。比对过程中，算法会尝试从第一个字符开始，到最后一个字符结束，保证整个序列都参与比对。因此，它适合用于比较两个相似度较高、长度相似的序列。实际上，全局序列对比与局部序列对比的算法差异在于状态转移方程的scoring matrix不同。

全局序列对比的算法是基于动态规划（LCS问题）的Needleman—Wunchi算法，下面就来介绍该算法。

Pairwise sequence alignment 的目标

Pairwise sequence alignment的目标是找到两个序列之间的最佳匹配方式，允许错配（substitution）、插入（insertion）或删除（deletion）。我们的任务是根据给定的打分规则，找到得分最高的比对方式。

•匹配（match）：如果两个序列的字符相同，得分较高。

•错配（mismatch）：如果两个序列的字符不同，得分较低或者扣分。

•插入/删除（gap）：比对时，允许在一个序列中插入空位（gap），通常会受到罚分。

打分体系

在比对两个序列时，我们会为每一个操作（匹配、错配、插入/删除）分配不同的分数：

•匹配：给一个正分，表示两个字符相同。

•错配：给一个负分，表示字符不同。

•插入/删除（gap）：给一个负分，表示出现了缺失。

举例：

假设我们给打分规则如下：

•匹配：+1

•错配：-1

•插入/删除（gap）：-2

状态转移方程：

参考代码

局部序列对比问题

局部序列比对（Local Sequence Alignment） 是一种在两个序列中找到相似度最高的局部片段的方法，而不强制要求比对整个序列。它通过比较子序列，找到它们之间的最佳匹配。这在生物信息学中尤其有用，比如基因和蛋白质序列分析，因为即使两个生物序列整体差异较大，它们也可能共享某些相似的功能区域或保守区。

局部序列比对最常用的算法是 Smith-Waterman算法，这个算法允许我们找到两个序列中相似度最高的部分，忽略其他不相似的部分。

Smith-Waterman算法

Smith-Waterman算法 是最经典的局部比对算法，使用动态规划来寻找序列中相似的局部区域。它与全局比对（Needleman-Wunsch）算法类似，但有一个关键区别：它允许在比对矩阵中有零值，即忽略不相似的部分，并从局部得分最高的地方开始回溯，以获得相似度最高的子序列。

序列同一性和序列相似性

序列同一性（Sequence Identity）

定义：

序列同一性是指在两个比对序列中，相同位置上的字符完全相同的比例。字符可以是核苷酸（DNA或RNA中的A、T、C、G）或氨基酸（蛋白质中的20种不同氨基酸）。序列同一性表示的是精确匹配，即两个序列在某个位置上的字符必须完全一致，才会计入同一性计算。

计算公式：

•Number of Identical Matches：两个序列中位置上相同的字符数。 •Total Length of Alignment：比对后序列的总长度，包含gap（插入或缺失的空位）。

示例：

假设我们有两个比对的序列：

•序列1：AGCTGA •序列2：AGCTAA

计算序列同一性：

•相同字符：5个（AGCTA）。 •比对长度：6（包括所有字符）。

注意：

•Gap（空位）处理：比对中可能会出现gap，gap通常在进化或基因变异中代表插入或缺失。计算时需要决定是否包含gap。例如，在某些情况下，gap会降低序列同一性。 •序列同一性是一个严格的指标，只有当字符完全匹配时才会被计入。

应用场景：

•同源序列比对：用于判断两个序列是否来自同一个祖先基因。 •进化关系分析：较高的序列同一性通常表明序列具有较近的进化关系。 •序列验证：在基因编辑或克隆中，检查目标序列与设计序列是否完全相同。

序列相似性（Sequence Similarity）

定义：

序列相似性不仅关注序列中完全相同的字符，还包括在相同位置上具有相似化学性质或功能的字符替换。特别是在蛋白质序列中，不同氨基酸之间可能具有相似的物理或化学性质（如极性、疏水性、大小等），即使它们不同，也可以被视为“相似”。

计算公式：

•Number of Identical Matches：与序列同一性计算相同，表示完全匹配的字符数。 •Conservative Substitutions：指功能或化学性质相似的替换。例如，在蛋白质中，氨基酸如 Leucine (L) 和 Isoleucine (I) 都是疏水性的，因此可以被视为相似。 •Total Length of Alignment：比对的总长度，包含gap。

示例：

假设我们有两个蛋白质序列：

•序列1：AGCTGA •序列2：AGS-TGV •相同字符：5个（AGCTG）。 •保守替换：第6位 A 被替换为 V，在某些情况下可以认为它们具有相似的化学性质（疏水性）。

注意：

•保守替换（Conservative Substitutions）：计算序列相似性时，常用某些替换矩阵（如BLOSUM或PAM）来判断哪些氨基酸替换可以被视为相似。该类替换可能不会改变蛋白质的结构或功能。 •序列相似性计算较为灵活，可以捕捉到不同序列之间的潜在相似性，即使它们的字符并不完全匹配。

Sequence identity and the twilight-zone

通过图表和文字解释了序列同一性如何影响我们判断两个序列是否具有共同的进化祖先。

Safe Zone（安全区）：

•位于图的右上方，表示序列同一性较高（通常高于50%），且比对序列的长度也较长。

•解释：如果两个序列在较长的比对长度上保持较高的同一性，我们可以比较有信心地推断这两个序列具有共同的进化祖先（同源性）。

•结论：在安全区中的序列比对非常可信，较高的同一性（>50%）表明两个序列进化上可能有非常紧密的关系。

Twilight Zone（暮光区）：

•这是一个位于图中间的区域，通常序列同一性在20%到30%之间。这是一个存在不确定性的区域。

•解释：在这个区域，虽然序列间有一定的同一性，但这个同一性较低，导致我们无法确定两个序列是否真的具有同源性。在此区间内，仅靠序列同一性不足以推断进化关系，可能需要其他的补充证据（如结构比对、功能性实验）来确认它们的进化关系。

•结论：序列同一性在20%-30%时，单靠比对并不能给出明确的同源性结论，需要使用更多的数据或工具来进行验证。

Dark Zone（黑暗区）：

•位于图的左下方，表示序列同一性低（通常低于20%），且比对的序列较短。

•解释：在黑暗区中，序列间的同一性非常低，很难通过序列比对来判断它们是否同源。实际上，序列同一性接近随机比对结果。

•结论：当两个序列的同一性很低且比对长度较短时，我们几乎无法通过序列同一性来推断它们的进化关系。

Challenges and Difficulties

Appropriate gap penalties

Appropriate substitution matrices

Complexity in computation

What to do next

Construction of substitution matrices

Multiple sequence alignment

Database searches