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

混亂編碼法(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 的索引對照表

比較序列相似性的另一個常用方法是使用點矩陣，指出在垂直與水平方向放置不相同的兩個序列時，只要兩序列有相似之處會看到偏離對角線的線段，而不會看到對角線。

Last updated on 08/30/01