BLAST(生物資訊學)

生物資訊學中，BLAST（英語：BasicLocalAlignmentSearchTool）伊是一个用來比對生物序列的一級結構（親像卵白質的胺基酸序列抑是無仝基因的 DNA 序列）的算法。已經知影包括若是干序列的資料庫，BLAST 會當予研究者佇內底走揣佮其感興趣的序列仝款抑是類似的序列。比如講若某一種非人動物的一个以早未知的基因予人發現，研究者一般會佇人類基因組中做一个 BLAST 搜揣來確認人類敢是包括類似的基因（通過序列的相當）。 BLAST 演算法佮實現伊的程式由美國國家生物技術資訊中心（NCBI）的 Eugene Myers、Stephen Altschul、Warren Gish、David J . Lipman 佮 Webb Miller 博士開發 [一] 的。

研究者利用 BLAST 來解決的其他問題有：

佗一个細菌物種包含和胺基酸序列已經知影某卵白質有親緣的關係的卵白質？
予人定序的一段 DNA 佗位啊？
何種基因編碼的卵白質表現出頭拄仔被確定的某種結構抑是結構模體？

……等咧。

背景

BLAST 是一个被廣泛使用於分析生物資訊的程式，因為伊會當兼顧咱咧做搜揣的時陣的速度佮搜揣結果的精確度。因為當阮所欲搜揣的目標資料庫足大的時陣，速度就變成一項真需要考量的因素。佇咧像 BLAST 和 FASTA 遮的快速算法予人開發進前，阮是使用動態規劃算法來做資料庫的序列搜揣，這真正是足厚工的。BLAST 使用啟發式搜揣來揣出相關的序列，佇咧速度比完全干焦使用動態規劃大約欲上五十倍左右，猶毋過伊無像動態規劃會當保證搜揣著的序列（Database sequence）佮所欲揣的序列（Query sequence）之間的相關性，BLAST 的工課就是盡量揣出資料庫內底佮所欲查詢的序列相關的資訊爾爾，精確度較低一點仔。此外，BLAST 比 FASTA 較緊，因為乎 BLAST 只對較少出現抑是較重要的一寡關鍵字作閣較進一步的分析，而且 FASTA 是考慮所有共同出現佇咧所欲搜揣的序列佮目標序列的字。對下跤介紹的演算法會當閣較進一步的了解。

算法

遮咱若卵白質對卵白質序列搜揣所用的程式 BLASTP 之實做的步數，來了解 BLAST 咱這程式的主要思想。

一 .徙掉 Query 列中之低複雜度猶閣有串接重複現象的區域低複雜度是講由真少種類的元素（如胺基酸）所組成的一个區域；咧接重複現象是講佇一个 Query 序列內底，有兩段串連的區域𪜶組成的方式一模一樣。這兩種佇序列內底的區域可能會予 BLAST 揣出一寡雖然分數有夠懸，但是其實佮 Query 序列並無相關的順序列，所以佇咧咱執行搜揣進前，愛先共 Query 序列內底這兩種區域共伊濾掉。BLAST 的實際做法是，伊會共咱遮的區域用符號代替，而且咧搜揣的時陣無注意遮的符號。卵白質序列內底，就用 X 符號標示；而且 DNA 序列內底，著愛用 N 符號標示。低複雜度區域的這个所在，BLAST 是用一个叫做 SEG 的程式來處理卵白質序列，用叫做 DUST 的程式來處理 DNA 序列。另外一方面，卵白質序列內底共接重複現象的區域是使用 XNU 來處理。二 .將 Query 序列內底每一 k 個字的組合做一个表以 k=三為例（DNA 序列內底，阮則常以 k=十一做例），阮 "照排的" 將 Query 序列內底每三字的組合視做一个字組，並將遮的字組列佇一張字組表頂懸，一直到 Query 序列內底上尾一字嘛予人收入入入表上為止。由圖一會當閣較清楚的了解規个作法。三 .列出咱所關心的所有可能之字組這个步驟就是 BLAST 和 FASTA 之間真重要的一點無仝處。FASTA 關心所有佇第二步內底所揣出的字組表頂懸的每一个字組，伊會去搜揣資料庫內底的序列，看遮的序列敢有含遮的字組；毋過，BLAST 只對懸分的一寡字組有興趣，啊若這字組的分數是照順序較字組間的每一个字，閣配合著分矩陣（substitution matrix 抑是 scoring matrix）所產生的。所以，對每一个字組來講，可能有二十 ^ 三个 BLAST 可能關心的字組，當然遮的字組經過一个條件分數的篩選了後，只有少數字組會留下，這就是 BLAST 真正所關心的字組。比如講伊，若以 BLOSUM 六十二為著分矩陣，著 PQG 分別和 PEG 以及 PQA 較所得的分數是十五以及十二分，若有十三，著 PEG 會留落來並且予人用佇了後的步數，而且 PQA 無予人考慮。（佇咧 DNA 序列的搜揣內底，咱對匹配的字是加五分，彼不匹配的是扣四分。）四 .將遮的經篩選了後賰的高分字組織是快速搜揣樹的結構這是為著欲予程式較快速的比對遮的高分字組和資料庫內底的序列是毋是有完全匹配（exact match）的情形。五 .著逐个 Query 序列內底的字組重複步數已經到四，並且得著所有相應的高分字組六 .掃對資料庫內底落來的序列，看有共賰的懸分字組完全匹配的情形無 BLAST 會揣資料庫序列內底敢有高分字組出現，像佇第三步揣出來 PEG。若掃對有完全匹配的情形發生，這个完全匹配的位置就是阮了後愛對 Query 序列佮資料庫序列做無間縫的區域排比（ungapped local alignment）的起點。七 .共遮的完全匹配的所在擴展為高分序著（high-scoring segment pair , HSP）

舊版的乎 BLAST 會對這个匹配的位置，分別向左右去擴展，一直到比出來的分數開始變細為止。圖二闡述了這个概念。
為著閣較有效率，新版的 BLAST 予人開發出來，叫做 BLAST 二抑是講 Gapped BLAST。為著欲維持搜揣的靈敏度，BLAST 使用較低的坎值以留下較濟的懸分字組，因此第三步的懸分字組表會變較長。接咧，若圖三中以 X 代表的匹配字組是佇仝一个對倒落去正爿起去對角線頂懸，而且𪜶的距離是小於一个戶橂值 A，則這兩个匹配的位會結合做一个閣較長的區域。最後咧，這个新的區域會用舊版 BLAST 向左右擴展的方式來延伸做 HSP，啊若這个 HSP 的分數仝款嘛是用了分矩陣來評分每一个比對的情形，共遮的分數加加起來，就佮進前揣高分字組的方法仝款。

八 .共所有的分數有夠懸的 HSP 列出來所有分數比某一个由經驗法則推測出來的坎值 S 之 HSP 攏將被列出。這个戶橂值 S 是由檢視兩个無相關的序列去作大量大量無夠的區域排比會來的分數之分佈，進一步推測出 S 該按怎制定以保證予人留落來的 HSP 攏有一定程度的意義。九 .評估遮的留落來的 HSP 𪜶的分數敢有啥物意義 BLAST 會利用 Gumbel extreme value distribution ( EVD ) 這極值的分佈，來評估講每一个 HSP 分數的統計意義（已經有人證明兩个無相關的序列去作區域排比的時陣，無考慮 gap 的使用，做出來的分數攏會呈現 Gumbel EVD 的狀況；考慮 gap 的使用時間，該結論猶未予人證明）。根據 Gumbel EVD 所推測出來的理論，一个分數 S 大於抑是等於 Gumbel EVD 內底某一个值 x 的機率是 $ p \ left ( S \ geq x \ right )=一-\ exp \ left (-e ^ {-\ lambda \ left ( x-\ mu \ right ) } \ right ) $ ，其中 $ \ mu={ } ^ { \ left [\ log \ left ( Km'n'\ right ) \ right] } \ ! \ ! \ diagup \ ! \ ! { } _ { \ lambda } \ ; $ 統計變數 $ \ lambda $ 和 $ \ mathrm { K } $ 是由 Query 序列去佮大量予人挐絞絞（Globeal or local shuffling）的一个資料庫序列作無間縫區域排比所形成的 Gumbel EVD，才由這來評估出遮的統計變數。統計變數 $ \ lambda $ 和 $ \ mathrm { K } $ 決定所使用的得分矩陣佮間罰罰值（Gap penalties），閣有序列的元素組成份。至於 m』和 n』是分別是 Query 序列佮資料庫序列的有效長度（Effective length）。有效長度的由來是因為佇兩序列排比中，若排比的起點倚近其中一个序列的結尾時陣，著這个排比真歹有機會形成一个好的排比，這號做那際效應（[Edge effect http : / / www . ncbi . nlm . nih . gov / BLAST / tutorial / Altschul 影一 . html # head 七]）。所以，愛利用共原始序列的長度經過一寡修剪來彌補邊際效應，達成較好的統計估測（注意，做序列的長度攏差不多兩百个時陣，那際效應通常會當予人無注意）。予人修正過了長度是 $ m'\ approx m-{ \ frac { \ left ( \ ln { \ mathrm { K } mn } \ right ) } { \ mathrm { H } } } $ $ n'\ approx n-{ \ frac { \ left ( \ ln { \ mathrm { K } mn } \ right ) } { \ mathrm { H } } } $（注意 n 是所有資料庫中序列長度的總和）, 其中 $ \ mathrm { H } $ 是講兩个無相關的序列去作無間隔區域排比了後，每一个排比對平均所得的分數，這佮咱所使用的得分陣密切相關。Altschul 和 Gish 翁婿提供了阮遮的統計變數的參考值，如 $ \ lambda=空九三一八 $、$ \ mathrm { K }=空七一三 $、佮 $ \ mathrm { H }=空九四空 $，遮會當使用的得分矩陣是 BLOSUM 六十二。使用遮的參考值去作統計意義的估測其實毋是講誠準。經過以上分析，咱可能揣一个佮 Query 序列相關的資料庫序列，紲落來咱愛計算這个資料庫序列的向望分數 E（Expect score），伊的意義是當阮對非常濟个無相關序列其中的兩个作無縫區域排比如時，所得的分數會懸於這个資料庫序列佮 Query 序列之間的 HSP 分數之一數。經由搜揣一个有 D 個序列的資料庫所得的期望分數 E 會當由下式來得著。 $ \ mathrm { E } \ approx 一-e ^ {-\ mathbf { p } \ left ( \ mathbf { S } \ geq \ mathbf { x } \ right ) } $ 甚至當 $ \ mathbf { p } < 空七一 $ 時，E 會當由泊松分佈閣較進一步簡省為 $ \ mathrm { E }=\ mathbf { p } \ mathrm { D } $ 注意遮用來估測 HSP 分數（無所在）的向望分數 E 佮最後一个彼號步數用來估測具有一个縫的區域排比分數的向望分數 E 是無仝款的。差別就是毋是有縫（Gap），所以古早的統計變數攏愛重新計算。十 .將一个資料庫序列中的濟个 HSP 區域結合做一个閣較長的排比有時，阮會佇一个資料庫序列內底揣著偌个 HSP 區域，紲落共𪜶結合做一个閣較長的排比序列，這提供 Query 序列佮資料庫序列之間相關性的另外一个證據。當阮欲比較遮的結合了後的差別跤步踏差啥人，有兩種方法予阮選。一種號做 Poisson 法則（Poisson method），另外一種號做總分法則（sum-of scores method）。假使講有兩个新結合出來的區域，𪜶個別的 HSP 分數分別是（六十五 , 四十）和（五十二 , 四十五）。 Poisson 法則是以啥人的低分比較懸來予評價，像（五十二 , 四十五）就比（六十五 , 四十）重要，因為四十五 > 四十；毋過，總分法著較重視（六十五 , 四十）這組，因為六十五 + 四十（一百空五）比五十二 + 四十五（九十七喔）大。舊版的乎 BLAST 是用 Poisson 法則，抑若新版的 BLAST 抑是講 WU-BLAST 使用總分法則。十一 .顯示 Query 序列佮所有進前揣著可能相關的資料庫序列進前有一个縫區域排比

舊版的乎 BLAST 干焦會當顯示出 Query 序列佮進前揣著的 HSP 區域之間的無縫區域排比，甚至做一个資料庫序列內底有偌个 HSP 嘛是仝款，干焦會分開顯示。
新版的 BLAST 就無親像舊版按呢，若是一个資料庫序列內底有偌个 HSP，則伊會當將遮的 HSP 統統包含進一个較大型的有一縫區域排比較。遮閣提醒一改，遮做出來有一个縫區域排比之分數嘛是用阮頭拄仔講的 Gumbel EVD 揣出的向望分數 E 來做評估講，但是遮的統計變數愛考量甲央罰罰值，所以和進前的向望分數 E 是無仝款的。

十二 .列出上一步驟中向望分數 E 低於咱所要求的坎值之資料庫序列

參考文獻

外部連結

NCBI-BLAST 頭頁
NCBI-BLAST 教程

參見

序列比對

BLAST(生物資訊學)

背景

算法

相關的各種程式

卵清-卵清 BLAST（blastp）

已經轉錄序列-卵清 BLAST（blastx）

卵清-已經轉錄序列 BLAST（tblastn）

已經轉錄序列-已經轉錄序列 BLAST（tblastx）

位置相關的迵天代 BLAST（PSI-BLAST）

PHI-BLAST

megaBLAST

RPS-BLAST

IgBLAST

GEO BLAST

參考文獻

外部連結

參見