本文介绍了基序发现问题和中间字符串问题。
我们知道,DNA调控元件往往是一段相似的DNA序列。理想情况下这些序列完全一致,比如下面这样:
图片引自《生物信息学算法导论》
但实际上,这些序列不会完全一样,总会有若干位点发生“变异”,从而不同,比如下面这样:
图片引自《生物信息学算法导论》
如果给定一组DNA序列(暂且假定它们长度相等),那么如何找出这些相似的序列呢?由此可以引出两个问题,即基序发现问题和中间字符串问题。
要说明基序
是什么,首先介绍一下序列剖面
(Profile)。
图片引自《生物信息学算法导论》
接下来我们给出一系列符号定义,以便下文的讨论:
同样地,要讲清楚中间字符串问题,我们首先给出一些符号:
我们可以证明计算式子(1.2)和计算(2.2)是一回事。 首先,根据第一部分的定义,式(1.2)其实就是:
本文内容基于《生物信息学算法导论》,笔者所作的工作就是将算法推导过程补充详细。至于实现代码,我们会在后续文章中讨论。