序列比對演算法哪年出現

Ⅰ 基因組序列比對演算法介紹（一）

基因組重測序中序列比對介紹

重測序基因組數據比對，是指將測序儀下機fastq數據（NGS read序列，通常100-150bp），與人類參考基因組（reference）進行匹配，允許錯配（mismatch），插入缺失（indel），目的是在參考基因組找到序列最相似的位置，通常是基因組分析(包括 variation calling，ChIP-seq，RNA-seq，BS-seq)流程的第一步。

常用演算法

圖一

漢明距離（Hamming distance）表示兩個（相同長度）字對應位置不同的數量，我們以d（x,y）表示兩個字x,y之間的漢明距離。對兩個字元串進行異或運算，並統計結果為1的個數，那麼這個數就是漢明距離。圖中read1最佳位置的方法，就是通過查找最小漢明距離的實現的。

編輯距離（Edit distance）是針對二個字元串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字元串變成另一個字元串。圖中read3最佳位置，通過查找最我輯距離的方法實現。

圖二

全局比對（Global alignment）：全局比對是指將參與比對的兩條序列裡面的所有字元進行比對。全局比對在全局范圍內對兩條序列進行比對打分，找出最佳比對，主要被用來尋找關系密切的序列。其可以用來鑒別或證明新序列與已知序列家族的同源性，是進行分子進化分析的重要前提。其代表是Needleman-Wunsch演算法。圖一中，read3使用全部比對。

局部比對（Local alignment）：與全局比對不同，局部比對不必對兩個完整的序列進行比對，而是在每個序列中使用某些局部區域片段進行比對。其產生的需求在於、人們發現有的蛋白序列雖然在序列整體上表現出較大的差異性，但是在某些局部區域能獨立的發揮相同的功能，序列相當保守。這時候依靠全局比對明顯不能得到這些局部相似序列的。其次，在真核生物的基因中，內含子片段表現出了極大變異性，外顯子區域卻較為保守，這時候全局比對表現出了其局限性，無法找出這些局部相似性序列。其代表是Smith-Waterman局部比對演算法。圖一中，read2使用局部比對。

圖三

Smith-Waterman演算法介紹

Smith-Waterman是由Temple F. Smith和Michael S. Waterman於1981年提出的一種進行局部序列比對（相對於全局比對）的演算法，用於找出兩個核苷酸序列或蛋白質序列之間的相似區域。該演算法的目的不是進行全序列的比對，而是找出兩個序列中具有高相似度的片段。S-W演算法基於動態規劃，它接受任意長度、任意位置、任意序列的對齊，並確定是否能找到最優的比對。

簡單地說就是，動態規劃找到問題中較小部分的解，然後把它們放在一起，形成整個問題的一個完整的最優最終解。

它優於BLAST和FASTA演算法，因為它搜索了更大的可能性，具有更高的敏感性。

S-W演算法不是一次查看整個序列，而是對多個長度的片段進行比較，尋找能夠最大化得分的片段。演算法本身本質上是遞歸的：

圖四

演算法步驟如下：

基因組分析***** 微信 公眾號推出 《50篇文章深入理解NGS》系列文章， 第三篇文章 《基因組序列比對演算法介紹（一）》，爭取每周更新一篇高質量生信干貨帖子。

關注 "基因組分析" 微信公眾號，了解最新最全生信分析知識。

Ⅱ 序列比對演算法

序列比對演算法是生物信息學領域中不可或缺的一部分，其主要目標是尋找序列之間的相似性，這在資料庫搜索、基因組分析和功能預測等應用中極為重要。在序列比較過程中，理解和掌握相似性、同源性概念以及序列比較的指標和演算法對於深入研究生物序列分析至關重要。

序列比較的基本概念涉及由ATCG（RNA為AUCG）組成的核酸序列和由氨基酸縮寫組成的蛋白質序列。這些序列通常以FASTA格式存儲，如圖1所示，其中第一行為序列名稱或注釋，之後為序列主體，每行60-80個字母，具體格式根據資料庫和文件類型而定。

在序列比較中，相似性與同源性是核心概念。相似性是指通過演算法或工具快速找到序列間的相似之處，這在大型資料庫中尤為關鍵。同源性則表明兩個序列具有共同的祖先，意味著它們在結構和功能上可能存在相似之處。通過序列的相似性，我們可以推斷未知序列的結構和功能，這是蛋白質功能預測等研究領域的重要工具。

同源性可以分為直系同源和旁系同源。直系同源是指不同物種間共享的序列，來源於同一個祖先序列；旁系同源則指由於物種內部基因復制而產生的序列差異。例如，人α珠蛋白、β珠蛋白和肌紅蛋白為旁系同源，而它們的基因也是旁系同源。

序列比較的指標包括一致度和相似度。一致度描述了在相同長度的序列中，對應位置上相同殘基的比例，而相似度則考慮了替換積分矩陣（subsitution matrix）統計的不同位置殘基之間的相似性量化關系。在計算相似度時，還需考慮序列不同長度的問題，通過引入空位罰分制度，使不同長度序列對齊後進行比較。

DNA序列替換記分矩陣包括等價矩陣、轉換—顛換矩陣和BLAST矩陣。等價矩陣簡單地以相同鹼基為正，不同鹼基為零，但由於其不考慮鹼基的理化信息，實際應用較少。轉換—顛換矩陣根據轉換和顛換發生的頻率不同，給予相應得分數，而BLAST矩陣則基於大量實際比對結果，優化了轉換和顛換的得分。

蛋白質替換記分矩陣主要有等價矩陣、PAM矩陣、BLOSUM矩陣、遺傳密碼矩陣和疏水矩陣。等價矩陣與DNA替換矩陣類似，簡單地以相同氨基酸為正，不同氨基酸為零。PAM矩陣基於進化原理，反映了自然界易接受的氨基酸替換頻率。BLOSUM矩陣則通過統計相似度大於特定閾值的序列，得到更為精確的替換得分矩陣。遺傳密碼矩陣和疏水矩陣則分別從密碼子變化和氨基酸疏水性變化的角度考慮序列的相似性。

雙序列比對操作實例展示了如何使用蛋白質序列比對網站，如Pairwise Sequence Alignment，結合選擇的替換記分矩陣，對人血紅蛋白的α和β亞基進行比對。通過計算得到的相似度、一致度和最終比對得分，有助於理解序列間的相似性和同源性。

序列比對的演算法包括打分矩陣法、動態規劃模型和Blast演算法。打分矩陣法通過枚舉所有可能的比對組合來尋找最優解。動態規劃模型則通過構建狀態轉移矩陣，以動態規劃的思想逐步求解最優比對路徑。Blast演算法則採用種子-延伸策略，快速查找局部相似性，並評估比對的顯著性，通過E值衡量隨機匹配的可能性。

全局比對和局部比對的區別在於，全局比對旨在尋找序列間的整體最優匹配，而局部比對則關注於識別具有高度相似性的局部序列區域。空位罰分的改進通過引入狀態的概念，使得動態規劃模型在空位開始與空位延伸之間進行更精確的區分。

BLAST演算法是序列比對的常用方法，它首先找到高度相似的種子片段，以此為基礎向兩端擴展比對，並通過統計顯著性評估比對質量，以避免假陽性結果。此外，BLAST還採取了屏蔽低復雜度區域和考慮相似鄰居words等策略，以提高速度和靈敏度。

隱馬爾可夫鏈（HMM）在序列比對中進一步引入了生成概率的概念，使得模型不僅考慮狀態轉移概率，還能預測觀察到的符號序列，從而在比對過程中提供更精確的分析。

綜上所述，序列比對演算法是生物信息學中的一項關鍵技術，通過理解相似性、同源性概念以及序列比較指標，結合不同演算法和策略，可以高效地分析和理解生物序列之間的關系，對生物功能預測、基因組比較和進化研究等領域具有重要意義。

Ⅲ 詳細介紹雙序列比對、blast 以及多序列比對的區別,以及均適用於哪些場 景

序列比對是將兩個或多個序列排列在一起，標明其相似之處。使用間隔表示未比對上，比對上的相同或相似的符號排列在同一列上。序列比對是生物信息學以及基因組學與進化的基礎之一，其基本思想是：在生物學中普遍存在的序列決定結構、結構決定功能的規律，通過將核酸序列或者蛋白質序列的一級結構看成由基本字元構成的字元串，通過序列比對我們可以找到相似的序列並由此發現生物序列中的功能、結構和進化信息。
全局比對：全局比對是指將參與比對的兩條序列裡面的所有字元進行比對。全局比對在全局范圍內對兩條序列進行比對打分，找出最佳比對，主要被用來尋找關系密切的序列。其可以用來鑒別或證明新序列與已知序列家族的同源性，是進行分子進化分析的重要前提。其代表是Needleman-Wunsch演算法。
局部比對：與全局比對不同，局部比對不必對兩個完整的序列進行比對，而是在每個序列中使用某些局部區域片段進行比對。其產生的需求在於、人們發現有的蛋白序列雖然在序列整體上表現出較大的差異性，但是在某些局部區域能獨立的發揮相同的功能，序列相當保守。這時候依靠全局比對明顯不能得到這些局部相似序列的。其次，在真核生物的基因中，內含子片段表現出了極大變異性，外顯子區域卻較為保守，這時候全局比對表現出了其局限性，無法找出這些局部相似性序列。其代表是Smith-Waterman局部比對演算法。
雙重序列比對：雙序列比對是指對兩條序列M和N進行比對，找到其相似性關系，這種尋找生物序列相似性關系的過程被稱為雙序列比對。其演算法可以主要分成基於全局比對的Needleman-Wunsch演算法和基於局部比對的Smith-Waterman局部比對演算法
多重序列比對：多序列比對是雙序列比對推廣，即把兩個以上字元序列對齊，逐列比較其字元的異同，使得每一列字元盡可能一致，以發現其共同的結構特徵的方法稱為多序列比對。多序列比對演算法可以分成漸進法和同步法。其可以發現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關系，主要用於分子進化關系，預測蛋白質的二級結構和三級結構、估計蛋白質折疊類型的總數，基因組序列分析等。
基因組比對：是多序列比對的一種特例，指對基因組范圍內的序列信息進行比對的過程。通過對不同親緣關系物種的基因組序列進行比較，能夠鑒定出編碼序列、非編碼調控序列及給定物種獨有的序列。而基因組范圍之內的序列比對，可以了解不同物在核苷酸組成、同線性關系和基因順序方面的異同，進而得到基因分析預測與定位、生物系統發生進化關系等方面的信息。
BLAST：BLAST[1]（Basic Local Alignment Search Tool）是在在1990年由Altschul等人提出的雙序列局部比對演算法，是一套在蛋白質資料庫或DNA資料庫中進行相似性比較的分析工具。BLAST是一種啟發式演算法，用於在大型資料庫中尋找比對序列，是一種在局部比對基礎上的近似比對演算法，可以在保持較高精度的情況下大大減少程序運行的時間。
演算法思想描述：
雙重序列比對主要分成以Needleman-Wunsch演算法為代表的全局比對和以Smith-Waterman局部比對演算法為代表的局部比對，BLAST是局部比對的一種推廣。多重比對演算法可以主要分成動態規劃演算法、隨機演算法、迭代法和漸進比對演算法。
（1）雙重序列比對：
Needleman-Wunsch演算法：該演算法是基於動態規劃思想的全局比對的基本演算法，動態規劃的比對演算法的比對過程可以用一個以序列S為列，T為行的(m+1)×(n+1)的二維矩陣來表示，用
sigma表示置換矩陣。
在計算完矩陣後，從矩陣的右下角單元到左上單元回溯最佳路徑（用箭頭表示），根據最佳路徑給出兩序列的比對結果。其中，斜箭頭表示2個殘基匹配，水平箭頭表示在序列S的相應位置插入一個空位，垂直方向的箭頭表示在序列T的相應位置插入一個空位。

Smith-Waterman演算法：該演算法是一種用來尋找並比較具有局部相似性區域的動態規劃演算法，這種演算法適用於親緣關系較遠、整體上不具有相似性而在一些較小的區域上存在局部相似性的兩個序列。該演算法的基本思想是：使用迭代方法計算出兩個序列的相似分值，存在一個得分矩陣M中，然後根據這個得分矩陣，通過動態規劃的方法回溯找到最優的比對序列。與全局比對相比，這種演算法的改變是把矩陣單元值為負者一律取為0，這是因為分值為負的比對喪失了比對的生物學意義，因此把得分為負值的子序列丟棄。

BLAST: BLAST演算法的基本思想是通過產生數量更少的但質量更好的增強點來提高比對的速度。演算法的原理主要分為以下五步：（1）過濾：首先過濾掉低復雜度區域，即含有大量重復的序列；（2）Seeding：將Query序列中每k個字組合成一個表，即將一個序列拆分成多個連續的『seed words』（通常蛋白質k=3，核酸k=11）；（3）比對：列出我們所關心的所有可能的字組，再配合置換矩陣給出高分值的字組並組織成快速搜索樹結構或者哈希索引，因此此步驟可以快速搜索出大數據集中的所有匹配序列，找到每個seed words在參考序列中的位置；（4）延伸：當找到seed words的位置後，接下來需要將seed word延伸成長片段，延伸過程中，得分值也在變化，當得分值小於閾值時即停止延伸，最後得到的片段成為高分片段對，HSP（High-scoring segment pair）；（5）顯著性分析，最後我們使用如下公式計算E值，E值衡量了在隨機情況下，資料庫存在的比當前匹配分數更好的比對的數目，因此可以用該值作為指標評價HSP比對序列的可信度。
其中，m是資料庫長度，n是query的長度，S是HSP分數，其他兩個參數是修正系數。

（2）多重序列比對

動態規劃演算法：其基本思想是將一個二維的動態規劃矩陣擴展到三維或者多維，多序列比對的積分是n個序列中兩兩進行比對所得積分之和。矩陣的維度反映了參與比對的序列數。這種方法對計算資源要求比較高[6]。
隨機演算法：主要包括遺傳演算法和模擬退火演算法，遺傳演算法是一類借鑒生物界進化規律演化來的全局意義上的自適應隨機搜索方法。當用遺傳演算法進行生物序列分析時，每一代包含固定數量的個體，這些個體用他們的適應度來評價。變異則模擬了生物進化過程中的偶然殘基突變現象。對產生的新一代群體進行重新評價、選擇、交叉、變異，如此循環往復，使群體中最優個體的適應度不斷提高，直到達到一個閾值，演算法結束。模擬退火的基本思想是用一物質系統的退火過程來模擬優化問題的尋優方法，當物質系統達到最小能量狀態時，優化問題的目標函數也相應地達到了全局最優解。這兩種方法都是對構造好的目標函數進行最優解搜索，但實際比對效果並不好[6,7]。
迭代法：迭代法的代表是Muscle[8], Muscle是一個新的漸進比對和迭代比對的綜合演算法，主要由兩部分構成，第一部分是迭代漸進比對：第一次漸進比對的目的是快速產生一個多序列比對而不強調准確率，以此為基礎再對漸進比對進行改良。經過兩次漸進比對，形成一個相對准確的多序列比對；第二部分是迭代比對：該過程類似於Prrp演算法[9]，即通過不斷的迭代，逐步優化最終比對結果。其主要特點包括：使用kmer counting進行快速的距離測量，使用一個新的圖譜比對打分函數進行漸進比對，使用依賴於數的有限分隔進行細化。
漸進比對演算法：該演算法以Feng和Doolittle提出的最為經典[10]。漸進比對演算法的基本思想是迭代地利用兩序列動態規劃比對演算法,先由兩個序列的比對開始，逐漸添加新序列，直到所有序列都加入為止。但是不同的添加順序會產生不同的比對結果。確定合適的比對順序是漸進比對演算法的一個關鍵問題。通常，整個序列的比對應該從最相似的兩個序列開始，由近至遠逐步完成。作為全局多序列比對的漸進比對演算法有個基本的前提假設:所有要比對的序列是同源的，即由共同的祖先序列經過一系列的突變積累，並經自然選擇遺傳下來的，分化越晚的序列之間相似程度就越高。因此，在漸進比對過程中，應該對近期的進化事件比遠期的進化事件給予更大的關注。由於同源序列是進化相關的，因此可以按著序列的進化順序，即沿著系統發育樹(指導樹)的分支，由近至遠將序列或已比對序列按雙序列比對演算法逐步進行比對，重復這一過程直到所有序列都己添加到這個比對中為止[10]。其三個步驟為：（1）利用雙序列比對方法對所有的序列進行兩兩比對，得到相似性分值；（2）利用相似性矩陣（或距離矩陣）產生輔助導向樹；（3）根據導向樹進行漸進比對。漸進比對演算法是最常用、簡單又有效的啟發式多序列比對方法，它所需時間較短、所佔內存較小，其演算法很多，主要有CLUSTAL W, T-Coffee和DiAlign等，其中 CLUSTAL W應用最廣泛。
應用：
類型+應用
雙重序列對比：判斷兩個序列的同源性和一致性。（1）全局多序列比對可以鑒別或證明新序列與己有序列家族的同源性;幫助預測新蛋白質序列的二級和二級結構，是進行分子進化分析的重要前提。適合序列相似性較高，序列長度近似時的比對；（2）局部比對考慮序列部分區域的相似性。局部多序列比對可以用來刻畫蛋白質家族和超家族。適合於未知兩個序列相似程度的，可能存在一些片段極其相似而另一些片段相異的序列比對情況。
多重序列比對：多重比對經常用來研究序列間的進化關系，構建進化樹；探究序列間的保守性。主要用於分子進化關系，預測蛋白質的二級結構和三級結構、估計蛋白質折疊類型的總數，基因組序列分析等。
基因組比對：通過對不同親緣關系物種的基因組序列進行比較，能夠鑒定出編碼序列、非編碼調控序列及給定物種獨有的序列。而基因組范圍之內的序列比對，可以了解不同物在核苷酸組成、同線性關系和基因順序方面的異同，進而得到基因分析預測與定位、生物系統發生進化關系等方面的信息。
其中，BLAST作為最重要的比對工具，意義特殊，拿出來單獨討論。BLAST可以分成Basic BLAST和 Specialized BLAST, BLAST包括常規的nucleotide blast, Protein blast和Translating blast；Specialize blast可以對特殊生物或特殊研究領域的序列資料庫進行檢索。