重磅新聞

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

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

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

近日深蘭科學院深度學習科學家方林博士在比對武漢新冠病毒與其他病毒（比如SARS）基因片段時，便利用了計算機科學中的next 值概念和相關算法大大提高了長序列對比的速度。
用普通方法，長序列比對的時間復雜度是：

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

長序列比對算法研究

深蘭科學院 方林博士

1、什么是長序列比對

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

其中，中括號擴起來的部分就是兩個字符串的相同部分。通過上下對應，我們可以很清楚地看到兩個序列中哪些部分相同，哪些部分不同。

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

2、長序列對比要解決的問題

2.1 耗時

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

兩個字符串中，長度為1的子串各有n個，于是要進行次字符比較。

長度為2的子串各有n-1個，于是要進行次匹配，平均每次匹配要進行1次字符比較。

……

長度為n的子串各有1個，要進行1次匹配，平均每次匹配要進行n/2次字符比較。

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

這意味著什么呢？這意味著如果長度增加2倍，則耗時增加16倍；如果長度增加10倍，則耗時就會增加10,000倍！

這是一個很可怕的數(shù)據(jù)。我用我的蘋果Mac Air筆記本電腦做了一下測試。先拿兩個長度為10的字符串測試，耗時6.69毫秒。可謂神速。然后用兩個長度為100的字符串測試，耗時0.526秒。這個速度也還不錯。等到我們用兩個長度為1,000的字符串測試時，足足等了半個多小時也沒有出來結果。為什么這樣？因為理論計算需要耗時5,000多秒，足足1個小時20多分鐘！

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

2.2 算法復雜

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

比如字符串AABABA和AACAABA，兩個字符串的頭兩個字符都是AA。那我們就讓這兩個字符匹配然后只比較剩余的部分行不行呢？不行！因為第二個字符串后面還有子串AABA可以跟第一個字符串的頭4個字符匹配，說不定后一種匹配更滿足用戶的需求呢？在對比兩個長度很長的字符串（比如基因序列）時，這種情況比比皆是。

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

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

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

比如，就拿上面提到的那兩個字符串AABABA和AACAABA來說，我們可以先試著用AA匹配AA，最后看看這樣匹配的結果是什么。比如說這樣匹配的得分是100分，那么接著我們再考慮用AABA匹配AABA，假設得分是120，那么我們最終就采用后一個方案。

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

對于耗時這個根本問題，我們需要另外找到思路。

3、序列快速比對算法

3.1 簡單方法

我們的目標不是一下子解決序列比對問題，而是先看一個簡單一點的問題：如何在一個字符串中查找一個子串。比如字符串ABABAAB中子串ABA的位置是3。

計算機科學中，這個算法稱為“字符串匹配”算法，其目的是在一個字符串中查找另一個字符串。前者稱為主串，后者稱為子串。這個算法中有一個“next值”概念。什么是next值？就是在匹配字符時，如果當前字符不匹配我們應該怎樣重新定位子串。

是不是不好理解？沒關系，別著急。我們看一個給定的子串：

AAAAB

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

AAABAAAABBBCCA

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

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

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

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

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

3.2、next值

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

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

第二步，子串往右挪了一位，子串的第1個字符與主串的第2個字符對齊：

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

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

令人吃驚的是，此時仍然不必對比子串的第1個字符與主串的第3個字符，因為他們注定相等。為什么？因為上面第2）個事實告訴我們主串的頭3個字符是AAA，這意味著子串的第1個字符與主串的第3個字符注定相等。所以我們只需對比子串的第2個字符與主串的第4個字符：

令人“崩潰”的是，這一步對比還是注定失敗的。因為上述事實1）已經(jīng)告訴了我們主串的第4個字符不是A！所以我們應該再次把子串往右挪一位，變成這樣：

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

此時，我們才真正開始了字符對比。也就是說，對于子串AAAAB來說，當?shù)?個字符不匹配時，應該把子串往右挪4位：

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

比如，利用上表，我們試圖在主串ABABAAABBAAAABBB中找子串AAAAB：

第1步：

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

第2步：

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

第3步：

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

第4步：

第1個字符不匹配，往右挪1位。

第5步：

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

3.3、快速比對算法

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