Genomic sequence databases, like GenBank, EMBL, are widely used by molecular biologists for homology searching. Because of the long length of each genomic sequence and the increase of the size of genomic sequence databases, the importance of efficient searching methods for fast queries grows. The DNA sequences are composed of four kinds of nucleotides, and these genomic sequences can be regarded as the text strings. However, there is no concept of words in a genomic sequence, which makes the search of the genomic sequence in the genomic database much difficult. Approximate String Matching (ASM) with k errors is considered for genomic sequences, where k errors would be caused by insertion, deletion, and replacement operations. Filtration of the DNA sequence is a widely adopted technique to reduce the number of the text areas (i.e., candidates) for further verification. In most of the filter methods, they first split the database sequence into q-grams. A sequence of grams (subpatterns) which match some part of the text will be passed as a candidate. The match problem of grams with the part of the text could be speed up by using the index structure for the exact match. Candidates will then be examined by dynamic programming to get the final result. However, in the previous methods for ASM, most of them considered the local order within each gram. Only the (k + s) h-samples filter considers the global order of the sequence of matched grams. Although the (k + s) h-samples filter keeps the global order of the sequence of the grams, it still has some disadvantages. First, to be a candidate in the (k + s) h-samples filter, the number of the ordered matched grams, s, is always fixed to 2 which results in low precision. Second, the (k + s) h-samples filter uses the query time to build the index for query patterns. In this thesis, we propose a new approximate string matching method, the hash trie filter, for efficiently searching in genomic databases. We build a hash trie in the pre-computing time for the genomic sequence stored in database. Although the size q of each split grams is also decided by the same formula used in the (k + s) h-samples filter, we have proposed a different way to find the ordered subpatterns in text T. Moreover, we reduce the number of candidates by pruning some unreasonable matched positions. Furthermore, unlike the (k + s) h-samples filter which always uses s = 2 to decide whether s matched subpatterns could be a candidate or not, our method will dynamically decide s, resulting in the increase of precision. The simulation results show that our hash trie filter outperforms the (k +s) h-samples filter in terms of the response time, the number of verified candidates, and the precision under different length of the query patterns and different error levels.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0628105-151511 |
| Date | 28 June 2005 |
| Creators | Hsu, Min-tze |
| Contributors | Chien-i Lee, San-yi Huang, Ye-in Chang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0628105-151511 |
| Rights | not_available, Copyright information available at source archive |
Page generated in 0.0018 seconds