四进制的核苷酸串
2029年，某科学课老师正在讲脱氧核苷酸的内容。这位活泼的00后，当讲到DNA的结构的时候，想到：
脱氧核苷酸的A、G、C、T，难道不是一种四进制吗？假设A代表0，G代表1，C代表2，T代表3，互补的和为3。四进制不就是2位二进制吗？
她看到了脱氧核苷酸和二进制的关系，开始想更多的生物学与信息学的问题。
第二天，她在科学课上对学生讲基因工程的时候，讲到转录和翻译的问题。于是引出了下面的问题。
寻找正确的脱氧核苷酸串
我们假设有很长的一串DNA，它的内容是这样的：
AGGCACGTTCATGTTAAAGCCATATCTTAGTCCAGTATCATCAGCATGCTAAGTCGTCA……
假设在这串DNA中，只有找到AGCATG子串的时候，转录才会开始。我们将介绍两种寻找脱氧核苷酸串的方法。
一般来说，我们需要一个一个地比较，就像下面：
这种比较方法叫做BF算法，它很简单，但问题是它比较的次数很多，而且当上一次比较到不同的字符的时候，还要回去比较之前的字符。当字符数量多的时候，比较的次数将以几何级数增加。
KMP算法
于是我们引入一种新的算法，它可以减少不必要的回溯，同时根据已经匹配的长度选择快速移动的方法。
在这种情况下，我们需要对于子串（设定为t1t2t3……tn）引入一个next值的概念。我们规定，next[1]=0（第一个字符的next值为0），第j个字符的next值由下面决定。
next[j]=k，其中"t1t2……t(k-1)"=="t(j-k+1)t(j-k+2)……t(j-1)"。当k=j时，next[j+1]=next[j]+1，否则next[j+1]=next[k]+1。当没有满足"t1t2……t(k-1)"=="t(j-k+1)t(j-k+2)……t(j-1)"的k值时，next[j+1]=1。
这样的算法更加适合计算机操作，尤其是当字符更多，部分重复区段更多的时候，优势就很大了。例如这里，只需要比较到第12次就可以找到位于第43个字符的转录起点了。
寻找脱氧核苷酸串的拓展
当科学老师和数学老师、信息老师交流到DNA的结构和基因工程的时候，数学老师和信息老师感到很兴奋。原来我们熟悉的二进制，竟然在这肉眼几乎不可见的DNA中也存在，并且关系如此紧密。科学老师继续展开：
假如是在细菌的环状DNA中切割有效片段用于基因工程，应该怎么办？
其实道理是一样的，只是当环状的时候，我们通过把DNA扩充到原来的2倍来思考问题。就像下面：
可以看到，目标脱氧核苷酸串在起始点附近的时候，扩充到原来的2倍能够更好找到目标。
数学老师之后也给他的学生讲了类似的开锁问题，就是在密码锁中的锁芯中有01234567的八进制数字和开锁密码条，只有当锁芯对应的数字和密码对上时才能开锁。
信息老师也发现了这个关系，给学生们讲了DNA和计算机的关系，DNA就像是计算机的指令的存储，而特异的蛋白质充当读取内容的磁针的作用。转录翻译的过程，本质就是转写二进制编码的过程。
这些都说明了生物学、信息学与数学的联通性。
回到现实
2020年疫情网课期间，在数据结构的课堂上，曾经讲过核酸检测与KMP算法的关系。本文的故事虽然发生在未来，但类似的事情在现在已经发生着。脱氧核苷酸串的匹配已经在基因工程中应用，甚至存在于转录、DNA复制等生命运行的行为中。
核酸检测也是KMP算法的一个应用，KMP算法的高效性在数据量极大的脱氧核苷酸序列中获得了很大的发挥。
我们应该感谢D.E.Knuth、J.H.Morris和V.R.Pratt，他们创造的KMP算法，极大地帮助了生物学和信息学的发展，让生命也可以以信息化的方法解决问题。
