基於遺傳演算法的雙序列比對

1. 判別分析方法、聚類分析方法、HMM方法簡介

三個學分的通選課,A類
曾經作為力學系的限選課開出.
歡迎大二以上有數理基礎的同學選修.

《生物信息學演算法導論》課程介紹
課程英文名：Introction to Computational Biology
課程號：00331440
開課單位：力學系、理論生物學中心
開課教師：朱懷球
上課時間：每周四晚
上課地點：理教201
選課地點、時間：三教103，9月5日星期五上午8:00～12:00

一、課程設置目的及主要內容
隨著人類基因組計劃的不斷推進，運用理論模型和數值計算研究生命科學，已經成為一門 最吸引人的新興學科，是當今生命科學和自然科學的核心領域和最具活力的前沿領域之一 。生物信息學/計算生物學以現代分子生物學數據作為主要研究對象，發展理論模型和計算方法，揭示以基因組信息結構為主的生物復性，以及生長、發育、遺傳、進化等生命 現象的根本規律。本課程主要為具有數理背景的大學二年級以上本科生（含大二）和相關領域的研究生開設，偏重理論建模和演算法的學習。首先介紹當代生命科學的發展和現狀， 然後介紹計算生物學中幾種主要的研究方法，包括統計學方法、Markov過程模型、資訊理論方法、機器學習方法等，並結合當今生物信息學領域的最新進展，討論上述各種方法實際研究中的應用（包括基因序列信息分析、基因預測、分子進化及系統發育樹和蛋白質調控網路等重要問題）。 本課程注重學科交叉、融合，以介紹思想、方法為主，深入淺出，避免繁瑣、抽象的數學形式，啟發學生綜合運用數學、物理、工程科學和計算機知識的能力，拓寬知識面，了解學科前沿和最新進展，培養跨越生命科學、計算科學、數理科學等不同領域的「大科學」素質和意識，為今後選擇新興交叉學科領域進行深造奠定基礎。

二、課程大綱

第1章 緒論 （1學時）
從人類基因組計劃說起
計算生物學——後基因組時代的呼喚
計算生物學主要研究內容和方法
以生命科學為核心的「大科學」

第2章 生物學基礎 （5學時）
What is life？——從薛定鍔的思考到「雙螺旋」的發現
生命的演化和分類
生命的分子組成
遺傳的分子基礎
基因組與基因結構

第3章 生物信息資料庫和計算生物學主要問題 （3學時）
生物信息資料庫簡介
計算生物學主要問題之一：序列比對
計算生物學主要問題之二：核酸和蛋白質結構與功能預測
計算生物學主要問題之三：基因組序列分析
計算生物學主要問題之四：功能基因組相關信息分析

第4章 計算生物學的統計學方法 （10學時）
統計方法的基本概念
回歸分析方法及其應用
判別分析方法及其應用
聚類分析方法及其應用

第5章 計算生物學的Markov過程模型 （6學時）
Markov過程的基本概念
隱Markov模型（HMM）的基本原理
HMM模型的計算生物學應用

第6章 生物學的資訊理論基礎 （6學時）
信源與信息熵
離散信道與平均互信息
編碼理論簡介
生物遺傳信息的傳遞

第7章 遺傳演算法和人工神經網路方法簡介 （8學時）
遺傳演算法的基本原理和方法
遺傳演算法與人工生命模型
人工神經網路的基本概念
人工神經網路的模式識別演算法

第8章 生物信息學/計算生物學的若乾重要問題 （6學時）
基因預測演算法和軟體
分子進化與系統發育
基因調控網路

三、本課程考試方式

在老師指導下，結合所講內容進行學科調研，要求同學在期中、期末分別完成兩次調研論 文，論文題目不限。

2. 大數據處理的五大關鍵技術及其應用

作者 | 網路大數據

來源 | 產業智能官

數據處理是對紛繁復雜的海量數據價值的提煉，而其中最有價值的地方在於預測性分析，即可以通過數據可視化、統計模式識別、數據描述等數據挖掘形式幫助數據科學家更好的理解數據，根據數據挖掘的結果得出預測性決策。其中主要工作環節包括：

一、大數據採集技術

數據是指通過RFID射頻數據、感測器數據、社交網路交互數據及移動互聯網數據等方式獲得的各種類型的結構化、半結構化(或稱之為弱結構化)及非結構化的海量數據，是大數據知識服務模型的根本。重點要突破分布式高速高可靠數據爬取或採集、高速數據全映像等大數據收集技術;突破高速數據解析、轉換與裝載等大數據整合技術;設計質量評估模型，開發數據質量技術。

大數據採集一般分為：

大數據智能感知層：主要包括數據感測體系、網路通信體系、感測適配體系、智能識別體系及軟硬體資源接入系統，實現對結構化、半結構化、非結構化的海量數據的智能化識別、定位、跟蹤、接入、傳輸、信號轉換、監控、初步處理和管理等。必須著重攻克針對大數據源的智能識別、感知、適配、傳輸、接入等技術。

基礎支撐層：提供大數據服務平台所需的虛擬伺服器，結構化、半結構化及非結構化數據的資料庫及物聯網路資源等基礎支撐環境。重點攻克分布式虛擬存儲技術，大數據獲取、存儲、組織、分析和決策操作的可視化介面技術，大數據的網路傳輸與壓縮技術，大數據隱私保護技術等。

二、大數據預處理技術

完成對已接收數據的辨析、抽取、清洗等操作。

抽取：因獲取的數據可能具有多種結構和類型，數據抽取過程可以幫助我們將這些復雜的數據轉化為單一的或者便於處理的構型，以達到快速分析處理的目的。

清洗：對於大數據，並不全是有價值的，有些數據並不是我們所關心的內容，而另一些數據則是完全錯誤的干擾項，因此要對數據通過過濾「去噪」從而提取出有效數據。

三、大數據存儲及管理技術

大數據存儲與管理要用存儲器把採集到的數據存儲起來，建立相應的資料庫，並進行管理和調用。重點解決復雜結構化、半結構化和非結構化大數據管理與處理技術。主要解決大數據的可存儲、可表示、可處理、可靠性及有效傳輸等幾個關鍵問題。開發可靠的分布式文件系統(DFS)、能效優化的存儲、計算融入存儲、大數據的去冗餘及高效低成本的大數據存儲技術;突破分布式非關系型大數據管理與處理技術，異構數據的數據融合技術，數據組織技術，研究大數據建模技術;突破大數據索引技術;突破大數據移動、備份、復制等技術;開發大數據可視化技術。

開發新型資料庫技術，資料庫分為關系型資料庫、非關系型資料庫以及資料庫緩存系統。其中，非關系型資料庫主要指的是NoSQL資料庫，分為：鍵值資料庫、列存資料庫、圖存資料庫以及文檔資料庫等類型。關系型資料庫包含了傳統關系資料庫系統以及NewSQL資料庫。

開發大數據安全技術：改進數據銷毀、透明加解密、分布式訪問控制、數據審計等技術;突破隱私保護和推理控制、數據真偽識別和取證、數據持有完整性驗證等技術。

四、大數據分析及挖掘技術

大數據分析技術：改進已有數據挖掘和機器學習技術;開發數據網路挖掘、特異群組挖掘、圖挖掘等新型數據挖掘技術;突破基於對象的數據連接、相似性連接等大數據融合技術;突破用戶興趣分析、網路行為分析、情感語義分析等面向領域的大數據挖掘技術。

數據挖掘就是從大量的、不完全的、有雜訊的、模糊的、隨機的實際應用數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。

數據挖掘涉及的技術方法很多，有多種分類法。根據挖掘任務可分為分類或預測模型發現、數據總結、聚類、關聯規則發現、序列模式發現、依賴關系或依賴模型發現、異常和趨勢發現等等;根據挖掘對象可分為關系資料庫、面向對象資料庫、空間資料庫、時態資料庫、文本數據源、多媒體資料庫、異質資料庫、遺產資料庫以及環球網Web;根據挖掘方法分，可粗分為:機器學習方法、統計方法、神經網路方法和資料庫方法。

機器學習中，可細分為歸納學習方法(決策樹、規則歸納等)、基於範例學習、遺傳演算法等。統計方法中，可細分為:回歸分析(多元回歸、自回歸等)、判別分析(貝葉斯判別、費歇爾判別、非參數判別等)、聚類分析(系統聚類、動態聚類等)、探索性分析(主元分析法、相關分析法等)等。神經網路方法中，可細分為:前向神經網路(BP演算法等)、自組織神經網路(自組織特徵映射、競爭學習等)等。資料庫方法主要是多維數據分析或OLAP方法，另外還有面向屬性的歸納方法。

數據挖掘主要過程是：根據分析挖掘目標，從資料庫中把數據提取出來，然後經過ETL組織成適合分析挖掘演算法使用寬表，然後利用數據挖掘軟體進行挖掘。傳統的數據挖掘軟體，一般只能支持在單機上進行小規模數據處理,受此限制傳統數據分析挖掘一般會採用抽樣方式來減少數據分析規模。

數據挖掘的計算復雜度和靈活度遠遠超過前兩類需求。一是由於數據挖掘問題開放性，導致數據挖掘會涉及大量衍生變數計算，衍生變數多變導致數據預處理計算復雜性;二是很多數據挖掘演算法本身就比較復雜，計算量就很大，特別是大量機器學習演算法，都是迭代計算，需要通過多次迭代來求最優解，例如K-means聚類演算法、PageRank演算法等。

從挖掘任務和挖掘方法的角度，著重突破：

預測分析成功的7個秘訣

預測未來一直是一個冒險的命題。幸運的是，預測分析技術的出現使得用戶能夠基於歷史數據和分析技術(如統計建模和機器學習)預測未來的結果，這使得預測結果和趨勢變得比過去幾年更加可靠。

盡管如此，與任何新興技術一樣，想要充分發揮預測分析的潛力也是很難的。而可能使挑戰變得更加復雜的是，由不完善的策略或預測分析工具的誤用導致的不準確或誤導性的結果可能在幾周、幾個月甚至幾年內才會顯現出來。

預測分析有可能徹底改變許多的行業和業務，包括零售、製造、供應鏈、網路管理、金融服務和醫療保健。AI網路技術公司Mist Systems的聯合創始人、首席技術官Bob fridy預測:「深度學習和預測性AI分析技術將會改變我們社會的所有部分，就像十年來互聯網和蜂窩技術所帶來的轉變一樣。」。

這里有七個建議，旨在幫助您的組織充分利用其預測分析計劃。

1.能夠訪問高質量、易於理解的數據

預測分析應用程序需要大量數據，並依賴於通過反饋循環提供的信息來不斷改進。全球IT解決方案和服務提供商Infotech的首席數據和分析官Soumendra Mohanty評論道:「數據和預測分析之間是相互促進的關系。」

了解流入預測分析模型的數據類型非常重要。「一個人身上會有什麼樣的數據?」 Eric Feigl - Ding問道，他是流行病學家、營養學家和健康經濟學家，目前是哈佛陳氏公共衛生學院的訪問科學家。「是每天都在Facebook和谷歌上收集的實時數據，還是難以訪問的醫療記錄所需的醫療數據?」為了做出准確的預測，模型需要被設計成能夠處理它所吸收的特定類型的數據。

簡單地將大量數據扔向計算資源的預測建模工作註定會失敗。「由於存在大量數據，而其中大部分數據可能與特定問題無關，只是在給定樣本中可能存在相關關系，」FactSet投資組合管理和交易解決方案副總裁兼研究主管Henri Waelbroeck解釋道，FactSet是一家金融數據和軟體公司。「如果不了解產生數據的過程，一個在有偏見的數據上訓練的模型可能是完全錯誤的。」

2.找到合適的模式

SAP高級分析產品經理Richard Mooney指出，每個人都痴迷於演算法，但是演算法必須和輸入到演算法中的數據一樣好。「如果找不到適合的模式，那麼他們就毫無用處，」他寫道。「大多數數據集都有其隱藏的模式。」

模式通常以兩種方式隱藏:

模式位於兩列之間的關系中。例如，可以通過即將進行的交易的截止日期信息與相關的電子郵件開盤價數據進行比較來發現一種模式。Mooney說:「如果交易即將結束，電子郵件的公開率應該會大幅提高，因為買方會有很多人需要閱讀並審查合同。」

模式顯示了變數隨時間變化的關系。「以上面的例子為例，了解客戶打開了200次電子郵件並不像知道他們在上周打開了175次那樣有用，」Mooney說。

3 .專注於可管理的任務，這些任務可能會帶來積極的投資回報

紐約理工學院的分析和商業智能主任Michael Urmeneta稱:「如今，人們很想把機器學習演算法應用到海量數據上，以期獲得更深刻的見解。」他說，這種方法的問題在於，它就像試圖一次治癒所有形式的癌症一樣。Urmeneta解釋說:「這會導致問題太大，數據太亂——沒有足夠的資金和足夠的支持。這樣是不可能獲得成功的。」

而當任務相對集中時，成功的可能性就會大得多。Urmeneta指出:「如果有問題的話，我們很可能會接觸到那些能夠理解復雜關系的專家」 。「這樣，我們就很可能會有更清晰或更好理解的數據來進行處理。」

4.使用正確的方法來完成工作

好消息是，幾乎有無數的方法可以用來生成精確的預測分析。然而，這也是個壞消息。芝加哥大學NORC (前國家意見研究中心)的行為、經濟分析和決策實踐主任Angela Fontes說:「每天都有新的、熱門的分析方法出現，使用新方法很容易讓人興奮」。「然而，根據我的經驗，最成功的項目是那些真正深入思考分析結果並讓其指導他們選擇方法的項目——即使最合適的方法並不是最性感、最新的方法。」

羅切斯特理工學院計算機工程系主任、副教授shanchie Jay Yang建議說:「用戶必須謹慎選擇適合他們需求的方法」。「必須擁有一種高效且可解釋的技術，一種可以利用序列數據、時間數據的統計特性，然後將其外推到最有可能的未來，」Yang說。

5.用精確定義的目標構建模型

這似乎是顯而易見的，但許多預測分析項目開始時的目標是構建一個宏偉的模型，卻沒有一個明確的最終使用計劃。「有很多很棒的模型從來沒有被人使用過，因為沒有人知道如何使用這些模型來實現或提供價值，」汽車、保險和碰撞修復行業的SaaS提供商CCC信息服務公司的產品管理高級副總裁Jason Verlen評論道。

對此，Fontes也表示同意。「使用正確的工具肯定會確保我們從分析中得到想要的結果……」因為這迫使我們必須對自己的目標非常清楚，」她解釋道。「如果我們不清楚分析的目標，就永遠也不可能真正得到我們想要的東西。」

6.在IT和相關業務部門之間建立密切的合作關系

在業務和技術組織之間建立牢固的合作夥伴關系是至關重要的。客戶體驗技術提供商Genesys的人工智慧產品管理副總裁Paul lasserr說:「你應該能夠理解新技術如何應對業務挑戰或改善現有的業務環境。」然後，一旦設置了目標，就可以在一個限定范圍的應用程序中測試模型，以確定解決方案是否真正提供了所需的價值。

7.不要被設計不良的模型誤導

模型是由人設計的，所以它們經常包含著潛在的缺陷。錯誤的模型或使用不正確或不當的數據構建的模型很容易產生誤導，在極端情況下，甚至會產生完全錯誤的預測。

沒有實現適當隨機化的選擇偏差會混淆預測。例如，在一項假設的減肥研究中，可能有50%的參與者選擇退出後續的體重測量。然而，那些中途退出的人與留下來的人有著不同的體重軌跡。這使得分析變得復雜，因為在這樣的研究中，那些堅持參加這個項目的人通常是那些真正減肥的人。另一方面，戒煙者通常是那些很少或根本沒有減肥經歷的人。因此，雖然減肥在整個世界都是具有因果性和可預測性的，但在一個有50%退出率的有限資料庫中，實際的減肥結果可能會被隱藏起來。

六、大數據展現與應用技術

大數據技術能夠將隱藏於海量數據中的信息和知識挖掘出來，為人類的社會經濟活動提供依據，從而提高各個領域的運行效率，大大提高整個社會經濟的集約化程度。

在我國，大數據將重點應用於以下三大領域：商業智能 、政府決策、公共服務。例如：商業智能技術，政府決策技術，電信數據信息處理與挖掘技術，電網數據信息處理與挖掘技術，氣象信息分析技術，環境監測技術，警務雲應用系統(道路監控、視頻監控、網路監控、智能交通、反電信詐騙、指揮調度等公安信息系統)，大規模基因序列分析比對技術，Web信息挖掘技術，多媒體數據並行化處理技術，影視製作渲染技術，其他各種行業的雲計算和海量數據處理應用技術等。

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