FASTA和BLAST是目前功能最全，使用最廣的同源性數據庫搜索軟件包。它們在Needleman

的動態(tài)算法的基礎上做了很多技術上的改進, 如采用啟發(fā)性算法, 使得在精確度犧牲較小的情況下, 速度快了很多。

FASTA 是 D.J. Lipman and W.R. Person

在1985年提出一個全局聯配算法(FASTP?FASTN?FASTA)。{ Science 227, 1435-1441,

1985;?PNAS 85, 2444-2448,

1988}

BLAST(Basic Local Alignment Search Tool

) 是 D.J. Lipman 和 S.F. Altschul等人1990年提出的，最初被設計用于序列局部比對。 {J. Mol.

Biol. 215, 403-410, 1990}

兩個算法都經過多次改進，變得越來越相象。

下載 (79.77 KB)

3?小時前

下載 (84.34 KB)

3?小時前

第一步：將待研究序列(query

sequence)分解成一些重疊的，固定長度的 words (對于蛋白質序列，這種長度一般取 1 至 3 個殘基，DNA 序列取 4

至 6)，這種長度就稱為ktup (or: k-tuple)

例：?R K T U R K

R K TU

R K

K

T

T U

U R

· · ·

對每一條數據庫序列，作相同的處理。然后，尋找待研究序列和庫序列的共有words, 進而定出一些全同片段。

FASTA采用了一種稱為“hash” 或 “l(fā)ook-up

table”的技術來加快這個過程。

下載 (56.06 KB)

3?小時前

第二步： 選取一些得分超過一定閾值的連續(xù)全同片段對(比如說10 對)

，并使每對片段的alignment盡可能向兩端無gap地延伸(只要能使得分增加)，其中最高的相似性得分記為 “init1

score”.

下載 (21.54 KB)

3?小時前

第三步： 嘗試著將緊鄰的片段對連成一個更長，有更高得分(initn

score)的片段對(甚至可以有gap)，并去掉那些明顯不屬于最佳全局alignment 的片段對。

下載 (18.77 KB)

3?小時前

第四步：最后，在一定寬度(32個殘基)的“條帶”范圍內，用Needleman的動態(tài)規(guī)劃算法尋找最佳的全局alignment,

對應的得分成為“opt score” 。

下載 (21.67 KB)

3?小時前

第一步：和FASTA的做法一樣，將待研究序列分解成一些重疊的，固定長度的

words (這種長度在BLAST中稱為w，對于蛋白質序列，取w=3,

DNA序列取w=11)，不同的是，BLAST進一步選出那些配對時得分最少為T的words，形成一個擴展的word list,

以w=2, T=8為例

下載 (37.07 KB)

3?小時前

第二步：掃描數據庫序列，找出能和expanded list

的words完全匹配的地方。

下載 (16.26 KB)

3?小時前

第三步： 對于每一個匹配的 word,

向兩個方向盡量擴展alignment，直到不能再擴展(導致score下降)，這時得到的聯配片段對稱為 HSP (High

Scoring Sequence Pair )。設定一個閾值S，記下在數據庫搜索中所有得分超過S的 HSP

下載 (10.04 KB)

3?小時前

第四步： 對記下的HSP作統(tǒng)計學分析。

幾個參數和概念及設置

ktup：

嚴格的兩序列alignment是以“殘基”為單位進行的。但是為了提高速度，先找出那些完全匹配的片段，然后以這些片段為單位來進行alignment。要求的這種片段的最小長度就稱為Ktup值；

Ktup設置得小，則敏感度高，能找到哪些序列相似性不高，但確實有同源關系的序列，缺點是所花計算時間較長，并可能將一些無關的序列也找出來(假陽性)；ktup

大，則反之。

一般地，對于蛋白質查詢，ktup設為2，對于DNA，則設為6。

假設數據庫中的某條序列(seqX)中的某個片段全同于以下序列：

>QQQQ_2

ctcctatgagtgttaaccttgatgcctgaaagaactggaaattatgaagatagattcaga

毫無疑問，當用序列QQQQ_2 作為query

sequence來搜索數據庫時，肯定能找到庫序列seqX。

如果我們人為地將序列QQQQ_2

每5個殘基改變一個，序列變成QQQQ_3。

QQQQ_2:

ctcctatgagtgttaaccttgatgcctgaaagaactggaaattatgaagatagattcaga

QQQQ_3:

ctccaatgaatgttcacctagatgactgacagaaatggacattaagaagctagaatcagc

這時候，用序列QQQQ_3 作為query

sequence來搜索數據庫時，不管是FASTA還是BLAST，都找不到庫序列seqX，盡管實際上QQQQ_3同seqX的一個片段有高達80%的相似性

HSP

HSP 的定義： The pairs whose scores can not

be improved by extension or trimming are called high-scoring

segment pairs or HSPs.

E-value

稱為期望值，計算公式為：

E=K?m?n?e-λS

其意義為：若查詢序列為一條隨機序列，對于同樣的數據庫，有希望找到 E

條相似性得分為 S的HSP片段。

上面公式中的m?n

是搜索空間的大小，K和λ參數與打分系統(tǒng)有關，一般通過Monte Carlo模擬得出。

顯然，E的值越小，說明結果越有意義。當 E遠小于 1時，E值可看做幾率

E 值小于 0.01的序列可以認定為同源序列;

E值介于1和10之間的序列也是一些值得注意的序列。

進行蛋白質序列同源搜索時，E值上限的默認設置是10.0，進行核酸序列同源搜索時E值上限的默認設置是2.0 。

很多

FASTA和BLAST的版本和服務器允許用戶根據自己的需要設置E值上限。

總結

以上是生活随笔為你收集整理的cath数据库fasta备注_数据库（同源）搜索软件 FASTA 和 BLAST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。