English  |  正體中文  |  简体中文  |  Items with full text/Total items : 28607/40644
Visitors : 5302320      Online Users : 270
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/6630

Title: 基於四元樹結構比對的基因字串比對演算法
A Genomic Sequence Matching Algorithm with Edge-base Quadtree Pattern Matching
Authors: Chih-Yuan Chen
陳志遠
Contributors: NTOU:Department of Electrical Engineering
國立臺灣海洋大學:電機工程學系
Keywords: 基因序列;四元樹
Genomic Sequence;Quadtree;tree pattern match
Date: 2004
Issue Date: 2011-06-22T08:53:08Z
Abstract: 隨著DNA資料庫的產生,尋找相似序列的比對演算法成為許多研究人員所努力的目標。傳統的字串比對演算法,如Boyer More和Knuth-Morris-Pratt (KMP),在處理基因字串的比對上有一些缺點,例如效率較差、比對過程過於複雜,以及占用太多記憶體空間等。因此,許多針對基因序列比對的演算法相繼被提出,如 Suffix tree和ACGT-words tree等。 本論文針對Suffix tree太佔記憶體空間的問題及ACGT-words tree比對過程過於煩瑣的問題來加以改善。此外,我們的方法還能提供一個上述兩種基因字串比對演算法都無法處理的功能,即Multi-Pattern搜尋。
Since the inception of Human Genome Project back in 1990s researchers in multiple disciplines have been seeking for highly efficient sequence alignment algorithms. Because a genome sequence can be regarded as a text string, many string matching algorithms can indeed be use for the genome sequencing tasks. However, many well-known, traditional string matching algorithms such as the Boyer More and the Knuth-Morris-Pratt (KMP), when used to match the genome sequences are often plagued by inefficiency, computational complexity, and consumption of huge memory space. Therefore, algorithms tailored for genomic sequencing have attracted a new generation of algorithm designers. In this thesis, we focus our attention on improving the existing algorithms for genome sequence matching. We have successfully reduced the huge memory consumption of the suffix tree method. Also, by introducing a new quadtree pattern matching we are able to avoid the highly complicated matching process of the ACGT-words tree algorithm. Last but not least, our method performs multi-pattern searching, which is beyond the capability of the algorithms we set out to improve.
URI: http://ethesys.lib.ntou.edu.tw/cdrfb3/record/#G0M92530070
http://ntour.ntou.edu.tw/ir/handle/987654321/6630
Appears in Collections:

Files in This Item:

There are no files associated with this item.



All items in NTOUR are protected by copyright, with all rights reserved.

 


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback