全局序列比對演算法

『壹』 生物信息系統序列比對存入什麼數據

生物信息系統序列比對存入什麼數據
生物信息學在短短十幾年間，已經形成了多個研究方向，以下簡要介紹一些主要的研究重點。
序列比對
序列比對（Sequence Alignment）的基本問題是比較兩個或兩個以上符號序列的相似性或不相似性。從生物學的初衷來看，這一問題包含了以下幾個意義：從相互重疊的序列片斷中重構DNA的完整序列。在各種試驗條件下從探測數據（probe data）中決定物理和基因圖存貯，遍歷和比較資料庫中的DNA序列，比較兩個或多個序列的相似性，在資料庫中搜索相關序列和子序列，尋找核苷酸（nucleotides）的連續產生模式，找出蛋白質和DNA序列中的信息成分。序列比對考慮了DNA序列的生物學特性，如序列局部發生的插入，刪除（前兩種簡稱為indel）和替代，序列的目標函數獲得序列之間突變集最小距離加權和或最大相似性和，對齊的方法包括全局對齊，局部對齊，代溝懲罰等。兩個序列比對常採用動態規劃演算法，這種演算法在序列長度較小時適用，然而對於海量基因序列（如人的DNA序列高達10^9bp），這一方法就不太適用，甚至採用演算法復雜性為線性的也難以奏效。因此，啟發式方法的引入勢在必然，著名的BLAST和FASTA演算法及相應的改進方法均是從此前提出發的。
蛋白質比對
基本問題是比較兩個或兩個以上蛋白質分子空間結構的相似性或不相似性。蛋白質的結構與功能是密切相關的，一般認為，具有相似功能的蛋白質結構一般相似。蛋白質是由氨基酸組成的長鏈，長度從50到1000~3000AA（Amino Acids），蛋白質具有多種功能，如酶，物質的存貯和運輸，信號傳遞，抗體等等。氨基酸的序列內在的決定了蛋白質的3維結構。一般認為，蛋白質有四級不同的結構。研究蛋白質結構和預測的理由是：醫葯上可以理解生物的功能，尋找dockingdrugs的目標，農業上獲得更好的農作物的基因工程，工業上有利用酶的合成。直接對蛋白質結構進行比對的原因是由於蛋白質的3維結構比其一級結構在進化中更穩定的保留，同時也包含了較AA序列更多的信息。蛋白質3維結構研究的前提假設是內在的氨基酸序列與3維結構一一對應（不一定全真），物理上可用最小能量來解釋。從觀察和總結已知結構的蛋白質結構規律出發來預測未知蛋白質的結構。同源建模（homology modeling）和指認（Threading）方法屬於這一范疇。同源建模用於尋找具有高度相似性的蛋白質結構（超過30%氨基酸相同），後者則用於比較進化族中不同的蛋白質結構。然而，蛋白結構預測研究現狀還遠遠不能滿足實際需要。

『貳』 詳細介紹雙序列比對、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可以對特殊生物或特殊研究領域的序列資料庫進行檢索。

『叄』 序列比對的演算法有哪些在應用上各有何特點

首先你要明白——Clustalx的多序列比對演算法是基於雙序列比對的，它先將所有序列兩兩比對，然後根據兩兩比對結果構建指導樹，再根據指導樹依次添加相似度最高的

『肆』 什麼是多序列全局比對的累進演算法（三個步驟）

第一，所有的序列之間逐一比對（雙重比對）；第二，生成一個系統樹圖，將序列按相似性大致分組；第三，使用系統樹圖作為引導，產生出最終的多序列比對結果。

『伍』 如何通過生物信息學獲得一個基因家族的所有序列

如何通過生物信息學獲得一個基因家族的所有序列
序列比對其意義是從核酸、氨基酸的層次來比較兩個或兩個以上符號序列的相似性或不相似性，進而推測其結構功能及進化上的聯系。研究序列相似性的目的是通過相似的序列得到相似的結構或功能，也可以通過序列的相似性判別序列之間的同源性，推測序列之間的進化關系。序列比對是生物信息學的基礎，非常重要。
序列比對中最基礎的是雙序列比對，雙序列比較又分為全局序列比較和局部序列比較，這兩種比較均可用動態程序設計方法有效解決。在實際應用中，某些在生物學上有重要意義的相似性不是僅僅分析單條序列，只能通過將多個序列對比排列起來才能識別。比如當面對許多不同生物但蛋白質功能相似時，我們可能想知道序列的哪些部分是相似的，哪些部分是不同的，進而分析蛋白質的結構和功能。為獲得這些信息，我們需要對這些序列進行多序列比對。多重序列比對演算法有動態規劃演算法、星形比對演算法、樹形比對演算法、遺傳演算法、模擬退火演算法、隱馬爾可夫模型等，這些演算法都可以通過計算機得以解決。

『陸』 什麼時候需要利用生物信息學獲取核酸序列信息

什麼時候需要利用生物信息學獲取核酸序列信息
1.序列比對
序列比對其意義是從核酸、氨基酸的層次來比較兩個或兩個以上符號序列的相似性或不相似性，進而推測其結構功能及進化上的聯系。研究序列相似性的目的是通過相似的序列得到相似的結構或功能，也可以通過序列的相似性判別序列之間的同源性，推測序列之間的進化關系。序列比對是生物信息學的基礎，非常重要。
序列比對中最基礎的是雙序列比對，雙序列比較又分為全局序列比較和局部序列比較，這兩種比較均可用動態程序設計方法有效解決。在實際應用中，某些在生物學上有重要意義的相似性不是僅僅分析單條序列，只能通過將多個序列對比排列起來才能識別。比如當面對許多不同生物但蛋白質功能相似時，我們可能想知道序列的哪些部分是相似的，哪些部分是不同的，進而分析蛋白質的結構和功能。為獲得這些信息，我們需要對這些序列進行多序列比對。多重序列比對演算法有動態規劃演算法、星形比對演算法、樹形比對演算法、遺傳演算法、模擬退火演算法、隱馬爾可夫模型等，這些演算法都可以通過計算機得以解決。
2.資料庫搜索
隨著人類基因組計劃的實施，實驗數據急劇增加，數據的標准化和檢驗成為信息處理的第一步工作，並在此基礎上建立資料庫，存儲和管理基因組信息。這就需要藉助計算機存儲大量的生物學實驗數據，通過對這些數據按一定功能分類整理，形成了數以百計的生物信息資料庫，並要求有高效的程序對這些資料庫進行查詢，以此來滿足生物學工作者的需要。資料庫包括一級資料庫和二級資料庫，一級資料庫直接來源於實驗獲得的原始數據，只經過簡單的歸類整理和注釋；二級資料庫是對基本數據進行分析、提煉加工後提取的有用信息。
分子生物學的三大核心資料庫是GenBank核酸序列資料庫，SWISS-PROT蛋白質序列資料庫和PDB生物大分子結構資料庫，這三大資料庫為全世界分子生物學和醫學研究人員了解生物分子信息的組織和結構，破譯基因組信息提供了必要的支撐。但是用傳統的手工分析方法來處理數據顯然已經無法跟上新時代的步伐，對於大量的實驗結果必須利用計算機進行自動分析，以此來尋找數據之間存在的密切關系，並且用來解決實際中的問題。
3.基因組序列分析
基因組學研究的首要目標是獲得人的整套遺傳密碼，要得到人的全部遺傳密碼就要把人的基因組打碎，測完每個小的序列後再把它們重新拼接起來。所以目前生物信息學的大量工作是針對基因組DNA序列的，建立快速而又准確的DNA序列分析方法對研究基因的結構和功能有非常重要的意義。對於基因組序列，人們比較關心的是從序列中找到基因及其表達調控信息，比如對於未知基因，我們就可以通過把它與已知的基因序列進行比較，從而了解該基因相關的生理功能或者提供疾病發病機理的信息，從而為研發新葯或對疾病的治療提供一定的依據，使我們更全面地了解基因的結構，認識基因的功能。因此，如何讓計算機有效地管理和運行海量的數據也是一個重要問題。
4.蛋白質結構預測
蛋白質是組成生物體的基本物質，幾乎一切生命活動都要通過蛋白質的結構與功能體現出來，因此分析處理蛋白質數據也是相當重要的，蛋白質的生物功能由蛋白質的結構所決定，因此根據蛋白質序列預測蛋白質結構是很重要的問題，這就需要分析大量的數據，從中找出蛋白質序列和結構之間存在的關系與規律。
蛋白質結構預測分為二級結構預測和空間結構預測，在二級結構預測方面主要有以下幾種不同的方法：①基於統計信息；②基於物理化學性質；③基於序列模式；④基於多層神經網路；⑤基於圖論；⑥基於多元統計；⑦基於機器學習的專家規則；⑧最鄰近演算法。目前大多數二級結構預測的演算法都是由序列比對演算法BLAST、FASTA、CLUSTALW產生的經過比對的序列進行二級結構預測。雖然二級結構的預測方法其准確率已經可以達到80%以上，但二級結構預測的准確性還有待提高。
在實際進行蛋白質二級結構預測時，往往會把結構實驗結果、序列比對結果、蛋白質結構預測結果，還有各種預測方法結合起來，比較常用的是同時使用多個軟體進行預測，把各個軟體預測結果分析後得出比較接近實際的蛋白質二級結構。將序列比對與二級結構預測相結合也是一種常見的綜合分析方法。
蛋白質二級結構指蛋白質多肽鏈本身的折疊和盤繞的方式。二級結構主要有α-螺旋、β-折疊、β-轉角等幾種形式，它們是構成蛋白質高級結構的基本要素，常見的二級結構有α-螺旋和β-折疊。三級結構是在二級結構的基礎上進一步盤繞，折疊形成的。研究蛋白質空間結構的目標是為了了解蛋白質與三維結構的關系，預測蛋白質的二級結構預測只是預測蛋白質三維形狀的第一步，蛋白質折疊問題是非常復雜的，這就導致了蛋白質的空間結構預測的復雜性。蛋白質三維結構預測方法有：同源模型化方法、線索化方法和從頭預測的方法但是無論用哪一種方法，結果都是預測，採用不同的演算法，可能產生不同的結果，因此還需要研究新的理論計算方法來預測蛋白質的三維結構。
圖4.1 蛋白質結構
目前，已知蛋白質序列資料庫中的數據量遠遠超過結構資料庫中的數據量，並且這種差距會隨著DNA序列分析技術和基因識別方法的進步越來越大，人們希望產生蛋白質結構的進度能夠跟上產生蛋白質序列的速度，這就需要對蛋白質結構預測發展新的理論分析方法，目前還沒有一個演算法能夠很好地預測出一個蛋白的三維結構形狀，蛋白質的結構預測被認為是當代計算機科學要解決的最重要的問題之一，因此蛋白質結構預測的演算法在分子生物學中顯得尤為重要。
5.結束語
現如今計算機的發展已滲透到各個領域，生物學中的大量實驗數據的處理和理論分析也需要有相應的計算機程序來完成，因此隨著現代科技的發展，生物技術與計算機信息技術的融合已成為大勢所趨。生物學研究過程中產生的海量數據需要強有力的數據處理分析工具，這樣計算機科學技術就成為了生物科學家的必然選擇，雖然人們已經利用計算機技術解決了很多生物學上的難題，但是如何利用計算機更好地處理生物學中的數據仍是一個長期而又復雜的課題。

『柒』 序列比對的演算法過程

實際操作中利用計算機程序實現序列比對的基本演算法。序列比對不僅需要考慮子序列之間的匹配，而且需要對整個序列進行比較。也就是說，必須考慮兩個序列中所有殘基的匹配。這就意味著，不可能使所有殘基都能嚴格匹配。在這種情況下，序列比對中確定空位的過程變得十分復雜。
在進行序列兩兩比對時，有兩方面問題直接影響相似性分值：取代矩陣和空位罰分。 空位罰分是為了補償插入和缺失對序列相似性的影響，由於沒有什麼合適的理論模型能很好地描述空位 問題，因此空位罰分缺乏理論依據而更多的帶有主觀特色。一般的處理方法是用兩個罰分值，一個對插入的第一個空位罰分，如10－15；另一個對空位的延伸罰分，如1－2。對於具體的比對問題，採用不同的罰分方法會取得不同的效果。
對於比對計算產生的分值，到底多大才能說明兩個序列是同源的，對此有統計學方法加以說明，主要的思想是把具有相同長度的隨機序列進行比對，把分值與最初的比對分值相比，看看比對結果是否具有顯著性。相關的參數E代表隨機比對分值不低於實際比對分值的概率。對於嚴格的比對，必須E值低於一定閾值才能說明比對的結果具有足夠的統計學顯著性，這樣就排除了由於偶然的因素產生高比對得分的可能。

『捌』 序列比對的分類

把兩個以上字元序列對齊，逐列比較其字元的異同，使得每一列字元盡可能一致，以發現其共同的結構特徵的方法稱為多序列比對 。多序列比對問題其實是雙序列比對問題的推廣。
多序列比對的目標是使得參與比對的序列中有盡可能多的列具有相同的字元，即，使得相同殘基的位點位於同一列，這樣以便於發現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關系，主要用於分子進化關系，預測蛋白質的二級結構和三級結構、估計蛋白質折疊類型的總數，基因組序列分析等。
由於多序列比對能夠揭示雙序列比對所不能發現的序列微弱相似性、序列模式和功能位點，因而對蛋白質和核酸序列的結構、功能和進化研究更加有用。 1981年，由F. Smith 和 M.Waterman首次提出局部比對演算法，動態規劃方法通過較少的改動便可以用來識別匹配的子序列， 並且忽略匹配區域之前或之後的失配和空位;局部比對時，表中小於零的位置用零代替。主要用來考察兩序列的某些特殊片段。