序列比对（19）基序发现和中间字符串问题

本文介绍了基序发现问题和中间字符串问题。

引言：DNA调控元件

我们知道，DNA调控元件往往是一段相似的DNA序列。理想情况下这些序列完全一致，比如下面这样：

图片引自《生物信息学算法导论》

但实际上，这些序列不会完全一样，总会有若干位点发生“变异”，从而不同，比如下面这样：

图片引自《生物信息学算法导论》

如果给定一组DNA序列（暂且假定它们长度相等），那么如何找出这些相似的序列呢？由此可以引出两个问题，即基序发现问题和中间字符串问题。

一、基序发现问题

要说明基序是什么，首先介绍一下序列剖面（Profile）。

图片引自《生物信息学算法导论》

接下来我们给出一系列符号定义，以便下文的讨论：

二、中间字符串问题

同样地，要讲清楚中间字符串问题，我们首先给出一些符号：

三、两个问题是等价的

我们可以证明计算式子（1.2）和计算（2.2）是一回事。 首先，根据第一部分的定义，式（1.2）其实就是：

小结

本文内容基于《生物信息学算法导论》，笔者所作的工作就是将算法推导过程补充详细。至于实现代码，我们会在后续文章中讨论。