在这篇文章中，我们将介绍保守序列的概念，并描述它们的生物学意义。

然后，我们将看到如何将寻找保守序列的问题简化为在给定序列中找到最常见 K-mer 的问题，并进一步修改该问题以处理不匹配，从而使我们的问题在生物学上更合理。

最后，我们将看到一个简单的算法来解决不匹配 K-mer 的问题。

在进化生物学和遗传学中，保守序列是指代代发生在不同或相同物种中的相同或相似的 DNA 或 RNA 或氨基酸（蛋白质）序列。这些序列的组成变化很小，有时甚至几代都没有变化。

以下示例显示了跨物种的序列保守实际上是什么样的：

在这张图片中，我们可以看到哺乳动物组蛋白的氨基酸序列及其保守区域。

灰色表示的那些在所有物种中都是保守的，白色的差距往往随着不同物种的变化而变化。

在基因组中多处发现保守的翻译和转录相关序列

发现核糖体中的某些 RNA 成分在不同物种中高度保守

发现 tmRNA 在多种细菌物种中是保守的

其他例子，如 TATA（重复区域）和 同源异型盒 (homeoboxes)（参与调节多种物种的胚胎发育）。

NCBI 提供的保守域数据库拥有关于不同生物体和基因组中保守序列的广泛资源。 它使用蛋白质特异性评分矩阵(PSSMs)来识别保守序列。

保守序列(converved sequences)可以分为两大类，直系同源和旁系同源。

当跨物种发现相同序列时，保守序列被称为直系同源

当同一基因组内几代发现相同序列时，则称为旁系同源

一项关于脊椎动物、蠕虫、昆虫和酵母基因组的研究 (PMCID:PMC1182216)

在 5 种脊椎动物（人、大鼠、小鼠、鸡和河豚）， 2 种隐杆线虫 (Caenorhabditis) 和 7 种酵母菌 (Saccharomyces)的全基因组比对中发现了保守元件

发现被分析的保守元件占人类基因组的 3%–8%，而在黑腹果蝇 (37%–53%)、秀丽隐杆线虫 (18%–37%) 和酿酒酵母 (47%–68%)基因组中所占的比例要高得多。

人类血红蛋白基因中的DNA序列在基因组的多个位置与黑猩猩的肌红蛋白基因序列相同。

我们经常看到核酸或氨基酸序列极度保守的情况，这些被称为超保守序列(ultra conserved sequences)。

例如，脊椎动物中的某些序列已经在差异很大的分类群中被发现。

在另一种情况下，我们拥有几乎所有生物体的普遍保守序列，例如 GTP结合延伸因子、 rRNA 和 tRNA 等。

在不同基因组中发现的保守序列可以是编码序列或非编码序列。

编码序列，氨基酸和核酸通常是保守的，以保留某种蛋白质的结构和功能。

这些序列经历最小的变化。当发生变化时，它们通常会用一种在生物化学上相似的氨基酸或核酸来代替。

类似地，其他与 mRNA 相关的核酸序列通常是保守的。

非编码序列，如核糖体位点、转录因子、结合位点等，也是保守序列。

保守序列 帮助我们找到不同生物和物种之间的同源性（相似性）。

使用保守序列的数据可以建立系统发育关系和树，并可以找到有效的祖先。

一个常见的例子是保守序列 16S RNA ，用于重建各种细菌门(Bacterial Phyla)之间的系统发育关系。

保守序列 还可用于标记遗传疾病和突变的起源。通过比较具有特定保守序列的基因组，我们可以轻松识别任何存在的异常。

在本节中，我们将看到给定单个 DNA 的一部分，我们如何找到短的保守序列。我们正在寻找的保守序列称为 Regulatory motifs

调控基序(Regulatory motifs) 通常位于基因上游的短核苷酸序列，是控制基因表达的短 DNA 片段（比如 15-30 个核酸），即基因被转录多少次，从而产生多少相应的蛋白质。

K-mers 是在输入字符串中找到的长度为 K 的子字符串。

在计算基因组学中，输入字符串表示氨基酸或核酸序列。例如:5-mers 表示长度为 5 的子字符串，7-mers 表示长度为 7 的子字符串。

我们将寻找 短保守序列(short conserved sequences) 的问题框定如下：

给定氨基酸或核酸的输入序列，找出出现频率最高的 K-mer。

举个例子，我们有以下数据，

序列: ACGTTGCATGTCGCATGATGCATGAGAGCT

K-mers: k = 4

预期结果: 输入序列中最常出现的 4-mer。

例子: 可以使用 滑窗技术(sliding window technique) 来找到所有的 K-mers。

让我们记下所有的 k-mers，

在这个例子中，我们看到 4-mers CATG 和 GCAT 是最常出现的 4-mers，它们各出现 3 次。

然而，从生物学实验中，我们发现保守序列有可能发生微小的变化。因此，我们需要扩展上述问题来处理不匹配的情况。

例如，ATCCGAT 和 ATCGGAA 有 2 个不匹配，一个在第 4 位，另一个在第 7 位。

让我们看看如何定义找到最常见的 k-mers 并允许不匹配的问题。

序列: ACGTTGCATGTCGCATGATGCATGAGAGCT

K-mers: K = 4，d = 1

预期结果: 最常见的 4-mer，每个 K-mean 允许 1 个不匹配。

例子: 采用了与上一个问题相同的示例序列。因此，所有可能的 4-mer 的列表不变。它们如下：

但是，最终结果会发生变化，因为现在我们必须考虑允许 1 次不匹配的所有可能性。

如果我们以 GATG 为例，上面的序列中有 5 个 k-mers 与 GATG 匹配，允许一个不匹配，即 GTTG、CATG、CATG、GATG 和CATG。

同样，ATGC 和 ATGT 也有 5 个匹配的 k-mer。

因此，我们对于允许 1 个不匹配的最常见 k-mer 的结果是 GATG、ATGC（匹配 TTGC、ATGT、ATGA、ATGC、ATGA）和 ATGT（匹配 ACGT、ATGT、ATGA、ATGC、ATGA）。

以下是解决上述问题的简单程序：