Similarity search

利用序列相似性搜尋資料庫

根據運算法( algorithms)，尋找相似的序列，也就是尋找符合下列條件的所有序列:
- 利用 blosum 或 PAM 等評分矩陣(scoring matrix) 決定得分
- 由誤配(mismatch) 的數目，插入空隙(gap insertion) 的數目，與空隙長度(gap length) 決定扣分(penalty)
搜尋轉譯 DNA 與蛋白質資料庫之差異
主要搜尋方法的比較
- heuristic methods: FastA 系列與 Blast 系列
- Smith-Waterman search: Simple, FrameSearch, Profile search

圖摘錄自GenCore使用者手冊,圖上有建連結

FastA 系列: 靈敏、但是速度較慢。只能以核酸序列比對核酸資料庫，或以蛋白質序列比對蛋白質資料庫。TFastA 則以蛋白質序列比對核酸序列資料庫。
Blast 系列: 搜尋速度很快，但在序列相似性較低時會有失誤，有可能會漏掉一些相關的序列。它是一組程式，會自動根據輸入的序列與所選擇的資料庫種類而執行適當的程式。在GCG的環境下使用私有的資料庫，而 NetBlast 可以選用美國 NCBI 的資料庫，這樣所比對的資料庫較完整，不像 GCG 的資料庫每兩個月才更新一次，在最近兩個月內新收錄的序列就無法被比對到。
Smith-Waterman 系列: 靈敏、但速度慢到必須用硬體加速才實用。

Dynamic programming 能有系統地尋找同源的序列，可是它的速度太慢。在資料庫搜尋上通常是利用經驗法則( rules of thumb ) 先挑出值得仔細分析的片段，再做 Needleman - Wunsch 的最佳化排列。像 FastA 這樣利用序列片段的相似性來推測可能有親緣關係的區域，再將少量找到的區域做嚴謹的區域性並列分析，可以節省許多計算的時間。這種利用法則加速搜尋的方法，稱之為「heuristic algorithm」。
雖然 FastA 已將搜尋資料庫所需的時間減少了許多，可是在資料庫不斷擴增的情形下，若有更快的方法能找到資料庫中的相似序列，將有助於瞭解 DNA 語言。 Blast ( Basic Local Alignment Search Tool ) 是根據統計理論所設計的，雖然它也是一種 heuristic 運算法，其計分方式卻與像 dynamic programming 一樣，能模擬找出突變最少的狀況的過程。這種 heuristic 運算法的計算速度約比 FastA 快一個數量級以上。

Querry	Target	GCG	GenWeb*	Comments
DNA	DNA	FastA, BlastN	FastA, BlastN (gapped)
Protein	Protein	FastA, BlastP	FastA, BlastP (gapped)
Protein	DNA	TFastA, TBlastN	TFastA, TBlastN (gapped)	Db automatically be translated in 6 frames⁺ before db search
DNA	Protein	BlastX	FastX, BlastX (gapped)	Seq. automatically be translated in 6 frames before db search
DNA	EST	TBlastX	TBlastX (ungapped)	Both seq. and db. automatically be translated in 6 frames before db search
DNA	DNA	-	TFastX	Frame-shifted alignment to translated DNA database

* Always choose "Blast2 Searches" in GenWeb to get a better performance.

⁺ Six frame translation: advantage; disadvantage.

Querry	Target	GCG	GenWeb	Comments
DNA	DNA	-	sw
Protein	Protein	-	sw
Protein	DNA	-	tswn	Db automatically be translated in 6 frames before db search
DNA	Protein	-	tswp	Seq. automatically be translated in 6 frames before db search

Querry	Target	GCG	GenWeb	Comments
DNA	Protein	framesearch	frame_n2p
DNA	Protein	-	frame+_n2p
Protein	DNA	framesearch	frame_p2n
Protein	DNA	-	frame+_p2n
Protein profile	DNA	-	proframesearch	Frame-shifted alignment between profile and db. seq.

Querry	Target	GCG	GenWeb	Comments
DNA profile	Protein	profilesearch	profilesearch
Protein profile	Protein	profilesearch	profilesearch
Protein profile	DNA	-	proframesearch	Frame-shifted alignment between profile and db. seq.
Protein profile	DNA	-	proframe+	An application included in the frame+_p2n model, which allowing for separate treatment of sequencing errors and insertions of complete codons. Provide a protein profile instead of a protein seq.
Protein profile	DNA	-	tprofilesearch	Db. is automatically translated in 6 frames

Last updated on 11/27/01