生物资讯是最近非常热门的一个研究方向所谓的生物资讯

1、簡介生物資訊是最近非常熱門的一個研究方向。所謂的生物資訊，其最終目標，便是要完全了解人類所有基因的秘密。而由於在生物資訊之中，儲存在資料庫中的DNA序列數量，是非常龐大的。因此，對生物學家來說，如何快速且有效率地從資料庫中，找出所需要的DNA序列，便成為一件非常重要的事情。在這個專題，我們設計一套系統。此系統基本上是要能提供使用者一個圖形化使用者介面，藉由此介面，依使用者所輸入的查詢字串，能夠對儲存在資料庫中DNA序列，做快速的搜尋，最後將搜尋後的結果呈現出來。而這個系統中，我們所使用的演算法是n-gram/2L index。1.現有 DNA 搜尋索引架構在進入我們專題的主題前，先介紹一下現有

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

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

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

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

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

7、一步我們要明字搜尋是如何透過這個架構達成的。首先，我們將欲搜尋的字分解成 n-Gram ，接著察看先前製作的前端引中我們想要的這些 n-Gram ，也是查詢字唯一可能出現的地點。如，我們在之前的子中，想要尋找 “ABBCD” 這個字，我們先分解 ABBCD 中全部可能的 2-Gram , AB、BB、BC、CD ，接著尋找我們製作的前端引中含有這些 2-Gram 的位置，如圖 7： 圖 7. 搜尋 - 第一步 接著使用外部集合併法 (merge outer join)，找出在我們之前製作的後端引中含有這些 n-Gram 的字，如圖 8： 圖 8. 外部集合併法 然而，這些含有 n-Gram 的

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

9、圖8的字串0並不符合，接著往下找最小的gram位置，當有相同id時,比較offset。在圖10中可以看到現在最小的是“BB”的10，所以將有相連的這三個拿出來做merge。merge後的結果與query做比對，發現字串1與欲搜尋的query有cover。把字串1放進 set Scover 中。依照這樣的步驟，最後 set Scover 中 有 字串1,2,3,5圖 10在使用外部集合併法並比對其是否可能含有欲搜尋之字後我們可進一步將需要搜尋後端引之減少。如上中，在做完此步驟後，我們發現有可能出現欲搜尋字的後端引，只有在字 1, 2, 3, 5 中。接著，我們再如法炮製剛剛對前端引做的事，對後端

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

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

12、字串會以不同的底色來突顯。圖註7 : 顯示開頭字母在文件中的位置。4.結論本系統已經可以成功利用n-gram/2L的方法建構出利於此演算法快速搜尋的資料庫，但在效率部分尚未與其他演算法比較，當搜尋字串較大的情形下，還沒達到理想的速度。在這部分上的程式碼上應還有需要改進的地方。在操作環境方面，目前以java視窗程式作為介面，稍作修改將可在網路上面以網頁的方式呈現，更方便使用者操作。參考資料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