Back to results list
Please use this identifier to cite or link to this item:
|Title:||Genomic sequence search and clustering using Q-gram||Authors:||Yuen, Man-chun||Keywords:||Hong Kong Polytechnic University -- Dissertations
|Issue Date:||2007||Publisher:||The Hong Kong Polytechnic University||Abstract:||With the advances in technologies, the amount of biological data such as DNA sequences and microarray data have been increased tremendously in the past decade. In order to obtain knowledge from the data, e.g., enhancing our understanding of the evolutionary changes and the causes of those severe diseases, one has to search for patterns from the databases of large size and high dimensionality. Information retrieval and data mining are powerful tools to extract information from the databases and/or information repositories. In the past several years, there have been attempts to apply these two branches of intelligent techniques to different bioinformatics applications. However, the performance of these existing techniques has not been optimized due to the characteristics of and requirements from biological data, e.g. extremely long genomic sequences with high dimensionality, and interpretable search/mining results. In this thesis, we focus on how to improve the searching and the clustering performance in genomic sequence databases. A Q-gram based genomic search (QgramSearch) algorithm and a Q-gram based genomic sequence clustering (QgramClust) algorithm are proposed. Our QgramSearch can efficiently search the homologous database sequences to a query sequence. It makes use of two novel hashing techniques to enhance the efficiency of indexing and retrieval. These two hashing techniques can better capture the overlapping characteristics in the Q-gram based index. As demonstrated by the experimental results, they run faster than the existing data structures. Besides, we measure the similarity of sequences based on the significance of Q-gram instead of the expensive sequence alignment. Thus, our search algorithm can run faster than the famous Blast algorithm. Following the idea of QgramSearch, a Q-gram based genomic sequence clustering (QgramClust) is proposed. In view of the challenge of expensive pairwise sequence comparison for large database sequences faced by the existing clustering algorithms, QgramClust employs the inverted index of Q-gram in sequence comparison so that the clustering process can be made efficient. Our clustering algorithm is a hybrid of partitioning method and hierarchical method. It quickly clusters a group of nearest neighbors and finally merges the clusters. Our experimental results show that QgramClust runs faster than BlastClust.||Description:||viii, 85 leaves : ill. (some col.) ; 30 cm.
PolyU Library Call No.: [THS] LG51 .H577M COMP 2007 Yuen
|URI:||http://hdl.handle.net/10397/3782||Rights:||All rights reserved.|
|Appears in Collections:||Thesis|
Show full item record
Files in This Item:
|b21657580_link.htm||For PolyU Users||162 B||HTML||View/Open|
|b21657580_ir.pdf||For All Users (Non-printable)||1.47 MB||Adobe PDF||View/Open|
Citations as of Oct 15, 2018
Citations as of Oct 15, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.