DNA序列完全比對搜尋系統 - 首頁.ppt

DNA序列完全比對搜尋系統 指導教授 : 張玉盈 教授 組員: 陳政浩、林峰世、陳俊仁 背景 Human Genome Project DNA研究 未來發展 DNA序列比對之難處 一段DNA序列的長度通常有數萬至數百萬個字元數。 DNA序列沒有「字」的概念。 簡介 DNA序列，可將其視為由4個字母A，C，G，及T所組成。  演算法使用n-gram/2L來實作DNA序列的完全比對。 優點: n-gram/2L是以n-gram inverted index為基礎，做出兩層的索引架構，有效地提昇效能。 Sliding Technique Index Building Algorithm 1. Extracting 4-subsequences 2. Building the back-end index 3. Extracting 2-grams 4. Building the front-end index 建構back-end-index 建構front-end-index Query Processing Cover in Query 當我們欲查詢的字串 Q 與文件中的字串 S 欲cover時，必定符合以下條件之一： （1） Q 的字尾與 S 的字首相符 （2） Q 的字首與 S 的字尾相符 （3） Q 包含整個 S （4） S 包含整個 Q 。 Query Processing Query Processing Query Processing Query Processing Query Processing Query Processing Query Processing 0. ABCD 1. BBCD 2. BCD 3. CDAB 4. ABC 5. AB Query Processing Query Processing Query Processing 開發環境 硬體環境:  CPU : AMD Athlon64 3000+ RAM : DDR 400 2GB 軟體環境: Windows XP Service Pack 2 JDK 1.5.0_09 MySQL 4.1.12a-nt NetBeans IDE 5.5 結論 實作時遇到的困難 心得 DEMO * * Query: A B B C D 2-gram: AB, BB, BC, CD Subsequence: 0 D C C B B A 4 3 2 1 0 matches ABCD Query: A B B C D 2-gram: AB, BB, BC, CD Subsequence: 0 D C C B B A 4 3 2 1 0 matches ABCD Query: A B B C D 2-gram: AB, BB, BC, CD Subsequence: 1 D C C B B B 4 3 2 1 0 matches BBCD A B B C D Sub1 SubX Query: A B B C D 2-gram: AB, BB, BC, CD Subsequence: 2 D C C B 4 3 2 1 0 matches BCD A B B C D Sub2 SubX Query: A B B C D 2-gram: AB, BB, BC, CD Subsequence: 3 B A D C 4 3 2 1 0 matches CDAB A B B C D A B Sub3 SubX Query: A B B C D 2-gram: AB, BB, BC, CD Subsequence: 4 C B B A 4 3 2 1 0 matches ABC Query: A B B C D 2-gram: AB, BB, BC, CD Subsequence: 5 B A 4 3 2 1 0 matches AB A B B C D Subx Sub5 Sub1: BBCD Sub2: BCDA Sub3: CDAB Sub5: DDAB Sub1: BBCD Sub2: BCDA Sub3: CDAB Sub5: DDAB Document 0 10 D 9 C 8 B B B A D D 7 6 5 4 3 B A D C B A D C B B 5 D C B A D C B A D D 4 C B A D C B A D C B 3 B A D D C B B A D C 2 A D C B A D C B A D 1 D C B B A D D C B A 0 9 8 7 6 5 4 3 2 1 0 Sub1: BBCD Sub2: BCDA Sub5: DDAB Docume