重磅新聞

深蘭科學(xué)院近日開發(fā)成功了一套獨(dú)特的AI算法，將病毒基因全序列對(duì)比的時(shí)間縮減到3分鐘，而蛋白序列的對(duì)比時(shí)間更是縮減到秒級(jí)。利用此獨(dú)特的AI算法和非線性動(dòng)力學(xué)混沌可視化理論，可進(jìn)一步研究新型冠狀病毒的蛋白靶標(biāo)，盡快找到新型冠狀病毒的藥物篩選。

比如SARS和新冠病毒(2019-nCov)的S蛋白對(duì)比只需3秒鐘，結(jié)論是兩者S蛋白的氨基酸序列的相似度為71.88%，最長(zhǎng)相同序列分別位于兩者的926和944位點(diǎn)，長(zhǎng)度為111。這項(xiàng)科研成果的意義在于基因和病毒學(xué)家可以據(jù)此進(jìn)行廣泛的基因?qū)Ρ�，從而確定病毒的族譜關(guān)系和進(jìn)化路徑，為后續(xù)疫苗和藥物研發(fā)提供依據(jù)。

目前深蘭科技決定向全社會(huì)開放這項(xiàng)功能，任何科學(xué)工作者只要向深蘭申請(qǐng)，即可根據(jù)所提供病毒基因序列或者序列片段，快速獲得對(duì)比結(jié)果、族譜關(guān)系圖和深蘭獨(dú)創(chuàng)的“病毒序列的功能性對(duì)比”。

近日深蘭科學(xué)院深度學(xué)習(xí)科學(xué)家方林博士在比對(duì)武漢新冠病毒與其他病毒（比如SARS）基因片段時(shí)，便利用了計(jì)算機(jī)科學(xué)中的next 值概念和相關(guān)算法大大提高了長(zhǎng)序列對(duì)比的速度。
用普通方法，長(zhǎng)序列比對(duì)的時(shí)間復(fù)雜度是：

這使得長(zhǎng)序列比對(duì)十分耗時(shí)。而長(zhǎng)序列比對(duì)在科研工作中用途十分廣泛，比如基因測(cè)序中的一個(gè)重要工作就是對(duì)兩個(gè)基因序列或者序列片段進(jìn)行比對(duì)，得出兩者之間哪些部分相同，哪些部分不同的結(jié)論。
下文將以科普的性質(zhì)介紹什么是序列比對(duì)、序列比對(duì)中的難題，以及next值概念，其中更多地是向大家介紹分析問題和解決問題的一般方法。不管你是不是技術(shù)和科研人員，不管你是不是計(jì)算機(jī)專業(yè)，希望本文都能對(duì)你有所啟迪。

長(zhǎng)序列比對(duì)算法研究

深蘭科學(xué)院 方林博士

1、什么是長(zhǎng)序列比對(duì)

給定兩個(gè)序列，所謂比對(duì)就是告訴我們這兩個(gè)序列哪些部分是相同的，哪些是不同的。比如字符串ABCACAABBC和BCBAABBA，他們的比對(duì)結(jié)果如下所示：

其中，中括號(hào)擴(kuò)起來的部分就是兩個(gè)字符串的相同部分。通過上下對(duì)應(yīng)，我們可以很清楚地看到兩個(gè)序列中哪些部分相同，哪些部分不同。

在下面的敘述中，我們都用字符串作為序列來說明。對(duì)于其他類型的序列，比如整數(shù)序列，我們的結(jié)論和方法同樣成立。

2、長(zhǎng)序列對(duì)比要解決的問題

2.1 耗時(shí)

首先，長(zhǎng)序列對(duì)比很耗時(shí)。如果采用普通方法，第一個(gè)字符串的每一個(gè)可能子串都要與第二個(gè)字符串的任意一個(gè)長(zhǎng)度相同的子串對(duì)比。假設(shè)兩個(gè)字符串的長(zhǎng)度都是n（當(dāng)然，實(shí)際比對(duì)時(shí)兩個(gè)字符串的長(zhǎng)度不一定相同，這里只是為了簡(jiǎn)化我們的討論而假設(shè)它們長(zhǎng)度相同），我們可以計(jì)算一下要進(jìn)行多少次比較。

兩個(gè)字符串中，長(zhǎng)度為1的子串各有n個(gè)，于是要進(jìn)行次字符比較。

長(zhǎng)度為2的子串各有n-1個(gè)，于是要進(jìn)行次匹配，平均每次匹配要進(jìn)行1次字符比較。

……

長(zhǎng)度為n的子串各有1個(gè)，要進(jìn)行1次匹配，平均每次匹配要進(jìn)行n/2次字符比較。

所以我們總共要進(jìn)行12 + 22 + …… +  + ，也就是n(n+1)(2n+1)/6次匹配。在計(jì)算機(jī)科學(xué)中，這種耗時(shí)的“復(fù)雜度”是。也就是說，耗時(shí)跟字符串長(zhǎng)度n的立方在一個(gè)數(shù)量級(jí)。更值得一提的是，如果我們把字符比較也考慮在內(nèi)，則時(shí)間復(fù)雜度達(dá)到。

這意味著什么呢？這意味著如果長(zhǎng)度增加2倍，則耗時(shí)增加16倍；如果長(zhǎng)度增加10倍，則耗時(shí)就會(huì)增加10,000倍！

這是一個(gè)很可怕的數(shù)據(jù)。我用我的蘋果Mac Air筆記本電腦做了一下測(cè)試。先拿兩個(gè)長(zhǎng)度為10的字符串測(cè)試，耗時(shí)6.69毫秒�？芍^神速。然后用兩個(gè)長(zhǎng)度為100的字符串測(cè)試，耗時(shí)0.526秒。這個(gè)速度也還不錯(cuò)。等到我們用兩個(gè)長(zhǎng)度為1,000的字符串測(cè)試時(shí)，足足等了半個(gè)多小時(shí)也沒有出來結(jié)果。為什么這樣？因?yàn)槔碚撚?jì)算需要耗時(shí)5,000多秒，足足1個(gè)小時(shí)20多分鐘！

當(dāng)然，你可以用計(jì)算服務(wù)器甚至超級(jí)計(jì)算機(jī)測(cè)試，結(jié)果肯定要好很多。但是一來，這樣的計(jì)算資源很昂貴；二來，這并沒有解決根本問題。比如，采用傳統(tǒng)算法用計(jì)算服務(wù)器全序列比對(duì)兩個(gè)病毒基因，耗時(shí)仍以小時(shí)計(jì)。

2.2 算法復(fù)雜

由于我們需要進(jìn)行全序列對(duì)比，所以，并不是找到一個(gè)相匹配的字符串就完事了。

比如字符串AABABA和AACAABA，兩個(gè)字符串的頭兩個(gè)字符都是AA。那我們就讓這兩個(gè)字符匹配然后只比較剩余的部分行不行呢？不行！因?yàn)榈诙�個(gè)字符串后面還有子串AABA可以跟第一個(gè)字符串的頭4個(gè)字符匹配，說不定后一種匹配更滿足用戶的需求呢？在對(duì)比兩個(gè)長(zhǎng)度很長(zhǎng)的字符串（比如基因序列）時(shí)，這種情況比比皆是。

那么怎么解決這樣的問題呢？計(jì)算機(jī)科學(xué)里有一個(gè)稱為“回溯”的方法。這個(gè)“溯”字表明這個(gè)方法跟河流有關(guān)。的確，當(dāng)我們解決算法問題時(shí)，就像沿著河流從上游往下游走，遇到河流分岔，意味著有多個(gè)方案供我們選擇。所謂回溯，就是我們先沿著第一個(gè)分岔往前走，如果這個(gè)分岔后來走得通那就沒什么好說的；如果走不通我們就回到分岔點(diǎn)，沿著第二個(gè)分岔往下走，……。以此類推，這樣不就行了嗎？

看起來好像是這么回事，但實(shí)際上并非如此簡(jiǎn)單。分岔的下游可能還有分岔，分岔的分岔還有分岔，……。所以我們要在每一個(gè)分岔點(diǎn)做好記錄，以便如果將來從下游回溯到這一點(diǎn)時(shí)我們知道下一步該往哪個(gè)分岔走。只有把所有可能的分岔都走到，我們才有可能得到最優(yōu)解。見下圖：

圖中紅色代表一條擁有眾多分岔點(diǎn)的河流，黑色代表我們所走過的路。

比如，就拿上面提到的那兩個(gè)字符串AABABA和AACAABA來說，我們可以先試著用AA匹配AA，最后看看這樣匹配的結(jié)果是什么。比如說這樣匹配的得分是100分，那么接著我們?cè)倏紤]用AABA匹配AABA，假設(shè)得分是120，那么我們最終就采用后一個(gè)方案。

即使不考慮如何記錄回溯點(diǎn)以及如何在回溯點(diǎn)恢復(fù)現(xiàn)場(chǎng)這樣復(fù)雜的技術(shù)問題，回溯法仍然不是我們的最優(yōu)選擇。因?yàn)榛厮莶�沒有解決耗時(shí)問題，而只是解決了怎么做的問題。也就是說，雖然我們知道至少要進(jìn)行數(shù)量級(jí)的比較，但是怎么比較我們不清楚。而回溯就是回答這個(gè)問題的。

對(duì)于耗時(shí)這個(gè)根本問題，我們需要另外找到思路。

3、序列快速比對(duì)算法

3.1 簡(jiǎn)單方法

我們的目標(biāo)不是一下子解決序列比對(duì)問題，而是先看一個(gè)簡(jiǎn)單一點(diǎn)的問題：如何在一個(gè)字符串中查找一個(gè)子串。比如字符串ABABAAB中子串ABA的位置是3。

計(jì)算機(jī)科學(xué)中，這個(gè)算法稱為“字符串匹配”算法，其目的是在一個(gè)字符串中查找另一個(gè)字符串。前者稱為主串，后者稱為子串。這個(gè)算法中有一個(gè)“next值”概念。什么是next值？就是在匹配字符時(shí)，如果當(dāng)前字符不匹配我們應(yīng)該怎樣重新定位子串。

是不是不好理解？沒關(guān)系，別著急。我們看一個(gè)給定的子串：

AAAAB

比如假設(shè)主串是AAABAAAABBBCCA，則從左往右數(shù)，子串出現(xiàn)的第一個(gè)位置是5：

AAABAAAABBBCCA

通常，你會(huì)怎樣在主串中尋找子串？方法不外乎是這樣的。第一步，把子串的第一個(gè)字符和主串的第一個(gè)字符對(duì)齊：

然后一個(gè)一個(gè)進(jìn)行對(duì)比，對(duì)比到第4個(gè)字符發(fā)現(xiàn)不匹配。于是，把子串往右挪一位，把主串的指針從第4位往左挪回到第2位。再一個(gè)一個(gè)按順序進(jìn)行匹配：

匹配到第3個(gè)字符時(shí)發(fā)現(xiàn)不匹配，再把子串往右挪一位。……，這個(gè)過程不斷重復(fù)，直到最后找到匹配串：

這個(gè)尋找子串的算法的時(shí)間復(fù)雜度是多少呢？假設(shè)主串的長(zhǎng)度是m，子串的長(zhǎng)度是n，則這個(gè)算法的復(fù)雜度是O(mn)�？雌饋砗孟褚膊皇翘珖樔�，但是別忘了，這只是尋找子串而已。對(duì)于字符串對(duì)比來說，尋找子串不過是最基礎(chǔ)的操作之一。反映到字符串比對(duì)上，時(shí)間復(fù)雜度就是。

產(chǎn)生這個(gè)問題的根本原因是，每當(dāng)字符不匹配時(shí)，我們不得不把主串和子串的指針挪回到開頭。下面，我們簡(jiǎn)單介紹一種主串指針永不回頭的匹配算法：基于next值的字符串匹配算法。

3.2、next值

回到上一節(jié)例子中主串和子串的第一步和第二步對(duì)比上，第一步：

注意：這一步告訴了我們兩個(gè)事實(shí)：1）主串的第4個(gè)字符肯定不是A；2）主串的頭3個(gè)字符一定是AAA。記住這兩個(gè)事實(shí)，我們下面會(huì)反復(fù)用到它們。

第二步，子串往右挪了一位，子串的第1個(gè)字符與主串的第2個(gè)字符對(duì)齊：

根據(jù)上述事實(shí)2)，我們已經(jīng)知道主串和子串的頭三個(gè)字符是相等的，所以，第二步對(duì)比時(shí)，實(shí)際上沒有必要再對(duì)比頭兩個(gè)字符了，它們注定相等，而是應(yīng)該直接對(duì)比子串的第3個(gè)字符與主串的第4個(gè)字符：

這樣是不是就省掉了兩次字符比較？可是，我們還能進(jìn)一步節(jié)省字符比較。根據(jù)上述事實(shí)1），主串的第4個(gè)字符不可能是A，這意味這一次字符比較也不用進(jìn)行了，它們注定不等。所以我們應(yīng)該把子串再往右挪一位，讓子串的第1個(gè)字符與主串的第3個(gè)字符對(duì)齊：

令人吃驚的是，此時(shí)仍然不必對(duì)比子串的第1個(gè)字符與主串的第3個(gè)字符，因?yàn)樗麄冏⒍ㄏ嗟�。為什么？因�(yàn)樯厦娴?）個(gè)事實(shí)告訴我們主串的頭3個(gè)字符是AAA，這意味著子串的第1個(gè)字符與主串的第3個(gè)字符注定相等。所以我們只需對(duì)比子串的第2個(gè)字符與主串的第4個(gè)字符：

令人“崩潰”的是，這一步對(duì)比還是注定失敗的。因?yàn)樯鲜鍪聦?shí)1）已經(jīng)告訴了我們主串的第4個(gè)字符不是A！所以我們應(yīng)該再次把子串往右挪一位，變成這樣：

基于同樣的分析，我們發(fā)現(xiàn)這一步對(duì)比仍然是注定失敗的！所以再次把子串往右挪一位，變成：

此時(shí)，我們才真正開始了字符對(duì)比。也就是說，對(duì)于子串AAAAB來說，當(dāng)?shù)?個(gè)字符不匹配時(shí)，應(yīng)該把子串往右挪4位：

這個(gè)4就是子串中第4個(gè)字符的“next值”。子串中其他字符的next值見下表：

比如，利用上表，我們?cè)噲D在主串ABABAAABBAAAABBB中找子串AAAAB：

第1步：

第2個(gè)字符不匹配，查表知道子串往右挪2位。

第2步：

仍然是第2個(gè)字符不匹配，子串再往右挪2位。

第3步：

這次是第4個(gè)字符不匹配，查表得子串往右挪4位。

第4步：

第1個(gè)字符不匹配，往右挪1位。

第5步：

這一次所有字符都匹配了。于是我們找到了子串。我們總共進(jìn)行了14次字符比較。而普通方法要進(jìn)行22次字符比較才能找到子串。當(dāng)子串很多很長(zhǎng)時(shí)，這種差距就很明顯了。

3.3、快速比對(duì)算法

我們的快速比對(duì)算法就是基于上述next值的。由于涉及到遞歸、回溯、問題分解、分枝定界等專業(yè)概念，比較復(fù)雜，所以這里就不再論述了。有興趣的讀者可以與我聯(lián)系。