生物資訊是最近非常熱門的一個(gè)研究方向所謂的生物資訊

1、簡(jiǎn)介生物資訊是最近非常熱門的一個(gè)研究方向。所謂的生物資訊，其最終目標(biāo)，便是要完全了解人類所有基因的秘密。而由於在生物資訊之中，儲(chǔ)存在資料庫(kù)中的DNA序列數(shù)量，是非常龐大的。因此，對(duì)生物學(xué)家來(lái)說(shuō)，如何快速且有效率地從資料庫(kù)中，找出所需要的DNA序列，便成為一件非常重要的事情。在這個(gè)專題，我們?cè)O(shè)計(jì)一套系統(tǒng)。此系統(tǒng)基本上是要能提供使用者一個(gè)圖形化使用者介面，藉由此介面，依使用者所輸入的查詢字串，能夠?qū)?chǔ)存在資料庫(kù)中DNA序列，做快速的搜尋，最後將搜尋後的結(jié)果呈現(xiàn)出來(lái)。而這個(gè)系統(tǒng)中，我們所使用的演算法是n-gram/2L index。1.現(xiàn)有 DNA 搜尋索引架構(gòu)在進(jìn)入我們專題的主題前，先介紹一下現(xiàn)有

2、的一些 DNA 搜尋索引架構(gòu)：（1）倒置索引 (inverted index)、（2）n-Gram index1.1 Inverted indexinverted index是種被常用在處理大型文字資料庫(kù)的資料結(jié)構(gòu)建置法，且在實(shí)作上的確有不錯(cuò)的成績(jī)。inverted index主要由兩部分組成，分別是（1）terms 和（2）Posting-lists（如圖 1）。圖 1. inverted indexinverted index 根據(jù)取用字的方式不同而有兩種模式：(1) Word-based inverted index (2) n-gram inverted index在這份專題中的演算法

3、是以 n-gram inverted index 作為基礎(chǔ)，以下我們將介紹n-gram inverted index。1.2 n-gram inverted indexn-gram inverted index 主要是被用於與語(yǔ)言特性無(wú)關(guān)的文字資料庫(kù)，也就是說(shuō)，欲搜尋的字串是由一個(gè)一個(gè)可分開(kāi)無(wú)語(yǔ)言意義的字母組成，而不是由字組成的（如圖 3），這種特性的索引架構(gòu)最適合用來(lái)搜尋基因資料庫(kù)以及東方語(yǔ)系資料庫(kù)。n-gram index是指將欲搜尋字串以固定長(zhǎng)度 n 的 window 一個(gè)一個(gè)字母的往右slide，以 3-gram index 為例，分解 “string data”將會(huì)得到六個(gè) Post

4、ing ListsExample 1:在圖二可以看到有關(guān) 3-gram index 的 posting lists.圖 2. n-Gram 倒置索引2. n-Gram/2L Inverted Index Structure 這次的研究報(bào)告中，我們要以韓國(guó)先進(jìn)資訊科技研究中心 (AITrc) 所提出的 n-Gram/2L演算法做為我們實(shí)作的目標(biāo)。第三章中我們將介紹這個(gè)演算法的運(yùn)作方式並簡(jiǎn)單分析此演算法 2.1 引架構(gòu) (Index Structure) n-Gram/2L 演算法的原乃是在原本的 n-Gram 引架構(gòu)上再做一次引架構(gòu)，其細(xì)節(jié)之後會(huì)詳加討，在此先簡(jiǎn)單敘述其工作架構(gòu)。圖 3為 n-G

5、ram/2L 的架構(gòu)示意圖： 圖3. n-Gram/2L 引架構(gòu) 其運(yùn)作的基本原為：將全部文件製成 n-Gram 引架構(gòu)後 (後端引 back-end index) ，再對(duì)此架構(gòu)製作一次引架構(gòu) (前端引 front-end index) 。在次的引架構(gòu)後，可有效篩選去除一些必要的引 (index) ，因此在引查詢時(shí)候，可以快尋找到結(jié)果，也可大減少製作引所需的空間。192.2 製作引 製作引的第一步就是先將入的文件分解成長(zhǎng)為 m 的字的集合。分解的方法為，以 m 為單位從文件的開(kāi)端移動(dòng)到末端，記中間遇到的任何長(zhǎng)為 m 的字，並將出現(xiàn)的位置記下，最後將它整成一份排序過(guò)、沒(méi)有重複的清單。此方法也稱為

6、 “sliding technique” 。如圖 4： 圖4. Sliding technique 值得注意的是，製作後端引架構(gòu)時(shí)，並需要一個(gè)字一個(gè)字地做sliding，我們只需要重複的字為 1 即可（圖 5）。此乃因?yàn)樵诘诙A段對(duì)後端引作引的時(shí)候會(huì)對(duì)引做 1-sliding technique ，屆時(shí)每個(gè) n-Gram 仍會(huì)被走訪一次，因此我們毋須在此做 1-sliding technique 。（圖 6） 圖5. 第一階段（製作後端引） 圖6 第二階段（製作前端引） The Algorithm of building the n-gram/2L index2.3 搜尋引 在製作完引之後，下

7、一步我們要明字搜尋是如何透過(guò)這個(gè)架構(gòu)達(dá)成的。首先，我們將欲搜尋的字分解成 n-Gram ，接著察看先前製作的前端引中我們想要的這些 n-Gram ，也是查詢字唯一可能出現(xiàn)的地點(diǎn)。如，我們?cè)谥暗淖又校胍獙ふ?“ABBCD” 這個(gè)字，我們先分解 ABBCD 中全部可能的 2-Gram , AB、BB、BC、CD ，接著尋找我們製作的前端引中含有這些 2-Gram 的位置，如圖 7： 圖 7. 搜尋 - 第一步 接著使用外部集合併法 (merge outer join)，找出在我們之前製作的後端引中含有這些 n-Gram 的字，如圖 8： 圖 8. 外部集合併法 然而，這些含有 n-Gram 的

8、字一定含有我們要的搜尋字，因此，我們可以透過(guò)比對(duì)合併出的字與我們欲搜尋的字，將可能包含的字過(guò)，以進(jìn)一步篩選。如圖 9.(a) 中欲搜尋的字之字首與某字之字尾相符，則某字尚有可能含有我們欲查詢的字；是如圖 9.(b) 中，欲查詢之字與某一字只有中間部分相符，則可發(fā)現(xiàn)字首或字尾必有字相符，如此某字中可能有我們欲查詢的字。 圖 9. 字重疊的情形 因此，我們可得到一定：當(dāng)我們欲查詢的字 Q 與文件中的字 S 欲cover時(shí)，必定符合以下四個(gè)條件之一：（1） Q 的字尾與 S 的字首相符 （2） Q 的字首與 S 的字尾相符 （3） Q 包含整個(gè) S ( 4 ) S 包含整個(gè) Q 。 由上面的定理可知

9、圖8的字串0並不符合，接著往下找最小的gram位置，當(dāng)有相同id時(shí),比較offset。在圖10中可以看到現(xiàn)在最小的是“BB”的10，所以將有相連的這三個(gè)拿出來(lái)做merge。merge後的結(jié)果與query做比對(duì)，發(fā)現(xiàn)字串1與欲搜尋的query有cover。把字串1放進(jìn) set Scover 中。依照這樣的步驟，最後 set Scover 中 有 字串1,2,3,5圖 10在使用外部集合併法並比對(duì)其是否可能含有欲搜尋之字後我們可進(jìn)一步將需要搜尋後端引之減少。如上中，在做完此步驟後，我們發(fā)現(xiàn)有可能出現(xiàn)欲搜尋字的後端引，只有在字 1, 2, 3, 5 中。接著，我們?cè)偃绶ㄅ谘u剛剛對(duì)前端引做的事，對(duì)後端

10、引中的字做外部集合併，可得到此文件中可能含有搜尋字的字以及它在文件中的位置，再將此字跟搜尋字做比對(duì)，看是否包含我們欲搜尋的字，如圖 11：圖 11. 使用外部集合併法比對(duì)文件中是否包含搜尋字最後，將每份文件中含有欲搜尋字的位置輸出，可完成搜尋工作。The alogrithm of processing queries using the n-gram/2L index2.4 n-gram/2L index 的優(yōu)點(diǎn) n-Gram/2L index 最大的優(yōu)點(diǎn)在於它改進(jìn) n-Gram index 記一些可以預(yù)知的多餘位移資訊的弊端。n-Gram/2L index 將這些位移資訊再做一次引，就可以節(jié)

11、那些用記重複資的空間，如圖 11： 圖 11. n-Gram/2L 對(duì)於 n-Gram 所做的改進(jìn)3.成果介面展示搜尋介面圖11圖註1 : 在此輸入欲搜尋之字串，按下右邊的Search啟動(dòng)搜尋。圖註2 : 搜尋結(jié)果會(huì)在這裡以清單的方式顯示。 顯示檔名以及該字串在文件中的位置。圖註3 : 顯示系統(tǒng)資訊。搜尋成功後的檢視圖 12圖註4 : 選取搜尋結(jié)果，雙擊會(huì)產(chǎn)生一個(gè)檢視文件的視窗(如圖13)。圖註5 : 註4所選取的文件資訊會(huì)在這裡顯示。文件檢視圖14這個(gè)是文件檢視的視窗，所有文件可以透過(guò)這個(gè)視窗來(lái)檢視。使用者可以根據(jù)需求調(diào)整一頁(yè)所要顯示的字?jǐn)?shù)，並利用下方的按鈕來(lái)進(jìn)行換頁(yè)。圖註6 : 比對(duì)相同的

12、字串會(huì)以不同的底色來(lái)突顯。圖註7 : 顯示開(kāi)頭字母在文件中的位置。4.結(jié)論本系統(tǒng)已經(jīng)可以成功利用n-gram/2L的方法建構(gòu)出利於此演算法快速搜尋的資料庫(kù)，但在效率部分尚未與其他演算法比較，當(dāng)搜尋字串較大的情形下，還沒(méi)達(dá)到理想的速度。在這部分上的程式碼上應(yīng)還有需要改進(jìn)的地方。在操作環(huán)境方面，目前以java視窗程式作為介面，稍作修改將可在網(wǎng)路上面以網(wǎng)頁(yè)的方式呈現(xiàn)，更方便使用者操作。參考資料1 Kim, M., Whang, K., and Lee, J., " n-gram/2L-Approximation: A Two-Level n-Gram Inverted Index Structure for Approximate String Matching," J