尋找兩個序列間的相似性,其實和研究色層分析圖譜間的相似性,或是 RNA 結構等都是同類的問題。要確保一定找的到存在的相似性,就必須使用有系統的方法,這樣若未找到相似的區域,才能很確定不是因為疏忽而未找到。
從頭到尾掃描,來確定字串出現的位置固然一定可找目標,可是速度較慢,序列越長時就會花越多的時間。在資料結構上雖會討論二元樹 (binary search tree)的方法,它在序列分析上卻不如「混亂編碼 (hashing)」法用的多。其實這個方法不但可用做字串搜尋,亦可用在轉譯遺傳密碼上,因為它的基本概念就是建立一對照表 (look up table)。這有些像外文書在書末都有索引,因此使用者不必直接到書中瀏覽,而可經由查閱索引,直接跳到字串出現之處,書越厚,利用索引就比直接瀏覽越快找到主題。
以 DNA 序列為例,可選取 n 個字為一個字,例如下圖 B 中的序列,是以兩個鹼基為一個字,可將序列用字的形式寫出。因為 DNA 只有四種鹼基,所以兩個鹼基只能組合出 16 個字,列於下列表格 ,而圖中各個字所在的位置亦可紀錄在表中。若想查詢〝CG〞出現的位置,只需比對這表上出現的字,即可知這個字出現在序列上 2, 8, 12, 17 這四個位置。
A. 5 10 15 20 TCGGA TTCGT ACGGT ACGGA TC B. 5 10 15 TC,CG,GG,GA,AT,TT,TC,CG,GT,TA,AC,CG,GG,GT,TA 20 AC,CG,GG,GA,AT,TC |
當然使用者可以建立 n 個鹼基所形成的「字」之對表。例如在尋找限制酵素切割位置時,若每個酵素都要掃描一次序列會花許多時間。可是若先建立一個對照表,則多個酵素均可使用此對照表找到切割位置,這樣搜尋的速度就快許多了。
表1 序列 A 的索引對照表
Dinucleotide |
Position |
Dinucleotide |
Position |
||
1 | GG |
3,13,18 |
9 |
GA |
4,19 |
2 |
TG |
- |
10 |
TA |
10,15 |
3 |
AG |
- |
11 |
AA |
- |
4 |
CG |
2,8,12,17 |
12 |
CA |
- |
5 |
GT |
9,14 |
13 |
GA |
- |
6 |
TT |
6 |
14 |
TC |
1,7,21 |
7 |
AT |
5,20 |
15 |
AC |
11,16 |
8 |
CT |
- |
16 |
CC |
- |
比較序列相似性的另一個常用方法是使用點矩陣,指出在垂直與水平方向放置不相同的兩個序列時,只要兩序列有相似之處會看到偏離對角線的線段,而不會看到對角線。
Last updated on 08/30/01