專題報告-資料庫系統實驗室.doc

簡介 生物資訊是最近非常熱門的一個研究方向。所謂的生物資訊，其最終目標，便是要完全了解人類所有基因的秘密。而由於在生物資訊之中，儲存在資料庫中的DNA序列數量，是非常龐大的。因此，對生物學家來說，如何快速且有效率地從資料庫中，找出所需要的DNA序列，便成為一件非常重要的事情。在這個專題，， DNA 搜尋索引架構 在進入我們專題的主題前，先介紹一下現有的一些 DNA 搜尋索引架構： （1）倒置索引 (inverted index)、（2）n-Gram index 1.1 Inverted index inverted index是種被常用在處理大型文字資料庫的資料結構建置法，且在實作上的確有不錯的成績。inverted index主要由兩部分組成，分別是（1）terms 和（2）Posting-lists（如圖 1）。 圖 1. inverted index inverted index 根據取用字的方式不同而有兩種模式： (1) Word-based inverted index (2) n-gram inverted index 在這份專題中的演算法是以 n-gram inverted index 作為基礎，以下我們將介紹n-gram inverted index。 1.2 n-gram inverted index n-gram inverted index 主要是被用於與語言特性無關的文字資料庫，也就是說，欲搜尋的字串是由一個一個可分開無語言意義的「字母」組成，而不是由「字」組成的（如圖 3），這種特性的索引架構最適合用來搜尋基因資料庫以及東方語系資料庫。 n-gram index是指將欲搜尋字串以固定長度 n 的 window 一個一個字母的往右slide，以 -gram index 為例，“string data”將會得到六個 Example 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-Gram/2L 的架構示意圖： 圖3. n-Gram/2L 索引架構 其運作的基本原理為：將全部文件製成 n-Gram 索引架構後 (後端索引 back-end index) ，再對此架構製作一次索引架構 (前端索引 front-end index) 。在兩次的索引架構後，可有效篩選去除一些不必要的索引 (index) ，因此在索引查詢時候，可以更快尋找到結果，也可大量減少製作索引所需的空間。 2.2 製作索引 製作索引的第一步就是先將讀入的文件分解成長度為 m 的字串的集合。分解的方法為，以 m 為單位從文件的開端移動到末端，記錄中間遇到的任何長度為 m 的字串，並將出現的位置記錄下來，最後將它整理成一份排序過、沒有重複的清單。此方法也稱為 “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 index 2.3 搜尋索引 在製作完索引之後，下一步我們便要說明字串搜尋是如何透過這個架構達成的。首先，我們將欲搜尋的字串分解成 n-Gram ，接著察看先前製作的前端索引中我們想要的這些 n-Gram ，也是查詢字串唯一可能出現的地點。例如，若我們在之前的例子中，想要尋找 “ABBCD” 這個字串，我們先分解 ABBCD 中全部可能的 2-Gram , AB、BB、BC、CD ，接著尋找我們製作的前端索引中含有這些 2-Gram 的位置，如圖 7： 圖 7. 搜尋 - 第一步 接著使用「外部聯集合併法 (merge outer join)」，找出在我們之前製作的後端