運算法 - 搜尋序列中字串的快速方法

混亂編碼(Hashing)

尋找兩個序列間的相似性,其實和研究色層分析圖譜間的相似性,或是 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

Word Length, ktup

當然使用者可以建立 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