四進制的核苷酸串
2029年惯悠，某科學課老師正在講脫氧核苷酸的內(nèi)容挟憔。這位活潑的00后，當講到DNA的結(jié)構(gòu)的時候拔莱，想到：
脫氧核苷酸的A立美、G匿又、C、T建蹄，難道不是一種四進制嗎碌更？假設A代表0，G代表1洞慎，C代表2痛单，T代表3，互補的和為3劲腿。四進制不就是2位二進制嗎旭绒？
她看到了脫氧核苷酸和二進制的關系，開始想更多的生物學與信息學的問題焦人。
第二天挥吵，她在科學課上對學生講基因工程的時候，講到轉(zhuǎn)錄和翻譯的問題花椭。于是引出了下面的問題忽匈。
尋找正確的脫氧核苷酸串
我們假設有很長的一串DNA，它的內(nèi)容是這樣的：
AGGCACGTTCATGTTAAAGCCATATCTTAGTCCAGTATCATCAGCATGCTAAGTCGTCA……
假設在這串DNA中矿辽，只有找到AGCATG子串的時候丹允，轉(zhuǎn)錄才會開始。我們將介紹兩種尋找脫氧核苷酸串的方法袋倔。
一般來說，我們需要一個一個地比較奕污，就像下面：
這種比較方法叫做BF算法萎羔，它很簡單，但問題是它比較的次數(shù)很多碳默，而且當上一次比較到不同的字符的時候贾陷，還要回去比較之前的字符。當字符數(shù)量多的時候嘱根，比較的次數(shù)將以幾何級數(shù)增加髓废。
KMP算法
于是我們引入一種新的算法，它可以減少不必要的回溯该抒，同時根據(jù)已經(jīng)匹配的長度選擇快速移動的方法慌洪。
在這種情況下，我們需要對于子串（設定為t1t2t3……tn）引入一個next值的概念。我們規(guī)定冈爹，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岸更。
這樣的算法更加適合計算機操作鸵膏，尤其是當字符更多，部分重復區(qū)段更多的時候怎炊，優(yōu)勢就很大了谭企。例如這里，只需要比較到第12次就可以找到位于第43個字符的轉(zhuǎn)錄起點了结胀。
尋找脫氧核苷酸串的拓展
當科學老師和數(shù)學老師糟港、信息老師交流到DNA的結(jié)構(gòu)和基因工程的時候攀操，數(shù)學老師和信息老師感到很興奮。原來我們熟悉的二進制秸抚，竟然在這肉眼幾乎不可見的DNA中也存在速和，并且關系如此緊密“溃科學老師繼續(xù)展開：
假如是在細菌的環(huán)狀DNA中切割有效片段用于基因工程，應該怎么辦吭敢？
其實道理是一樣的碰凶，只是當環(huán)狀的時候，我們通過把DNA擴充到原來的2倍來思考問題鹿驼。就像下面：
可以看到欲低，目標脫氧核苷酸串在起始點附近的時候，擴充到原來的2倍能夠更好找到目標畜晰。
數(shù)學老師之后也給他的學生講了類似的開鎖問題砾莱，就是在密碼鎖中的鎖芯中有01234567的八進制數(shù)字和開鎖密碼條，只有當鎖芯對應的數(shù)字和密碼對上時才能開鎖凄鼻。
信息老師也發(fā)現(xiàn)了這個關系腊瑟，給學生們講了DNA和計算機的關系聚假，DNA就像是計算機的指令的存儲，而特異的蛋白質(zhì)充當讀取內(nèi)容的磁針的作用闰非。轉(zhuǎn)錄翻譯的過程膘格，本質(zhì)就是轉(zhuǎn)寫二進制編碼的過程。
這些都說明了生物學河胎、信息學與數(shù)學的聯(lián)通性闯袒。
回到現(xiàn)實
2020年疫情網(wǎng)課期間游岳，在數(shù)據(jù)結(jié)構(gòu)的課堂上，曾經(jīng)講過核酸檢測與KMP算法的關系其徙。本文的故事雖然發(fā)生在未來胚迫，但類似的事情在現(xiàn)在已經(jīng)發(fā)生著。脫氧核苷酸串的匹配已經(jīng)在基因工程中應用唾那，甚至存在于轉(zhuǎn)錄访锻、DNA復制等生命運行的行為中。
核酸檢測也是KMP算法的一個應用期犬，KMP算法的高效性在數(shù)據(jù)量極大的脫氧核苷酸序列中獲得了很大的發(fā)揮。
我們應該感謝D.E.Knuth避诽、J.H.Morris和V.R.Pratt龟虎，他們創(chuàng)造的KMP算法，極大地幫助了生物學和信息學的發(fā)展沙庐，讓生命也可以以信息化的方法解決問題鲤妥。
