隨著高通量測序技術的迅猛發展，測序成本在不斷降低，測序效率在不斷提高。由此產生越來越多的生物序列數據，呈指數級爆炸增長，當然也包括基因序列或蛋白質序列。這些海量序列是後續生物信息分析的重要數據來源，一方面可以得到前所未有的生物信息，但另一方面也對數據分析研究者帶來了巨大挑戰，即數據的計算成本也在呈指數級增長。如何快速有效的分析海量序列數據是研究者面臨的首要問題。
其中蛋白質序列聚類是數據分析的重要研究內容，蛋白質序列聚類一方面可以對序列進行去冗餘操作，另一方面可以降低數據規模，進而方便數據存儲和後續的分析步驟。因此許多算法研究者開發了許多蛋白質序列聚類算法，其中CD-HIT和UCLUST（USEARCH聚類版本）是目前可以處理海量蛋白質序列的兩個經典聚類算法。目前這兩個算法的谷歌學術引用次數（截止2019年3月27號）分別為4314（CD-HIT）和8912（UCLUST），是目前序列聚類領域的代表性算法，而UCLUST速度和影響力更勝於CD-HIT，有一種唯我獨尊的地位。
這兩個算法都採用基於種子序列的啟發式聚類思想，如下圖所示。如果待比較序列和種子序列的距離（不相似性）小於給定閾值（如0.03），就將這條序列歸入到種子序列所屬類別。如果與所有種子序列的距離都大於給定閾值（如0.03），則將這條序列作為新的種子序列，加入到種子集合裡。每條種子序列就是每個類的代表序列，由於每條待比對序列只與種子序列比較，避免了序列間兩兩之間的比較，大大降低了計算時間。所以CD-HIT和UCLUST的計算時間複雜度為
O(KN)，其中N 是序列的總條數，K 是種子序列的條數。 但在蛋白質序列聚類過程中，作者發現序列個數K 的大小與序列條數N 在同一個數量級，導致計算時間仍然很大，有時候甚至接近於N，因此時間複雜度有可能為O(N*N)，並不是與N 線性增長。為了進一步降低運行時間，作者提出了Linclust算法，可將計算時間複雜度降低到O(N)，比CD-HIT和UCLUST快上百倍，極大提高聚類效率。
Linclust序列聚類算法步驟
下圖是Linclust算法的處理流程圖，可以看出總共分為5步，下面分別講解每一步的分析過程。
01
選取哈希值最小的兩個k-mer
對每條蛋白質序列，選取每條序列哈希值最小的兩個k-mer，途中有9條序列，最小哈希值的
k-mer用不同顏色標註。
02
初始預聚類
將含有共同k-mer的序列歸到一起，並選取長度最長的序列作為類的代表序列。
03
合併初始團
將代表序列相同的初始團合併。
04
確定類成員與代表序列間相似性
對於每個序列團，計算類成員與代表序列間的相似性。先用漢明距離（Hamming distance）和非空位局部比對（Ungapped local alignment）進行序列對過濾，即過濾掉序列相似性低的序列對。然後再用空位序列比對（Local gapped sequence alignment）確定最終相似性，若小於給定閾值（如97%），去除掉邊。最後只保留序列相似性大於給定閾值的邊。
05
序列類劃分
如果類成員都與代表序列有連邊，即相似性大於給定閾值，則劃分為一個類。否則屬於不同類別。
聚類結果比較
1 運行速度比較
在UniProt蛋白質序列數據庫進行比較，序列條數為61522444，比較的方法有CD-HIT、UCLUST等。下圖是聚類時間的結果比較，相似性閾值分別設置為50%，70%和90%。可以看出Linclust方法在50%相似性閾值下，運行速度比UCLUST快2300倍，比CD-HIT快4600倍，比MMseqs方法快460倍，比MASH快69000倍，比DIAMOND快1600倍。在90%相似性閾值下，比CD-HIT快62倍，比UCLUST快100倍，MMseqs快570倍。
下圖是運行時間的指數級曲線，可以推斷出Linclust運行時間與序列條數的關係是
O(N1.01次方)，UCLUST是O(N1.62次方)，CD-HIT是O(N2.75次方)。所以相對於其他方法，Linclust方法運行速度真正實現只與序列條數有關。
2 聚類靈敏度比較
聚類靈敏度（clustering sensitivity），作者定義為平均每個類的序列條數，平均序列條數越多，說明算法聚類靈敏度越好（a deeper clustering with more sequences per cluster implies a higher sensitivity to detect similar sequences）。下圖是不同方法的聚類靈敏度比較，可以看出Linclust方法聚類靈敏度也不錯。
2 聚類一致性（consistency）比較
可以反映聚類的質量，用聚類結果的GO註釋相似性分析，計算每個聚類單元裡類成員與代表序列間的GO相似性，得出每個類的平均（mean）和最低（worse）的GO相似性。如下圖所示，可以看出Linclust方法的聚類質量也不錯，高於其他方法。
總結
蛋白質序列聚類可以對數據進行去冗餘，降低海量序列數據規模，方便數據存儲和後續的序列信息挖掘。目前蛋白質序列聚類方法的時間複雜度為O(KN)，同時與序列條數和聚類個數有關，在實際聚類過程中運行時間較長。為此作者提出Linclust聚類算法，可將運行時間降低到O(N)，只與序列條數有關，進一步提高聚類效率。
參考文獻：
Steinegger M, Söding J. Clustering huge protein sequence sets in linear time.Nature communications, 2018, 9(1): 2542.
猜 您 喜 歡：
BMC Bioinformatics期刊三審被拒，如此悲催，如何避免？
NCBI數據下載速度50M/S以上？太快了吧
rHAT，國內首個三代序列比對算法
擴增子OTU聚類軟件：SeekDeep方法解讀(NAR方法文章)
mothur QIIME usearch，三足鼎立，誰主沉浮？
三代測序序列比對利器-BLASR，更小更快更方便
生信算法“八股文”，發表算法不再難！
END
關注生信算法｜掌握分析利器
長按二維碼關注
閱讀更多 微生物組 的文章
