Genomic sequence search and clustering using Q-gram

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.