DEVELOPING ALGORITHMS FOR FINDING THE SIMILAR MOTIF IN DNA SEQUENCES

Abstract

The problem of discovering the similar sub-sequences in a set of DNA biological sequences is an important problem of bio-technology. From the positions of similar sub sequences, we can discover the features of a group of similar function genes or the position for point mutation. In this paper, we analyze two problems of repeated and upproximate sub sequence discovery and employ the large set discovery algorithm for discovering the repeated sub-sequence and the genetic algorithm for discovering the approximate sub-sequence in a set of DNA biological sequence. In the repeated sub-sequence discovery algorithm, we consider the repeated sub-sequence as a large set and employed the Apriori-TiD algorithm (Agrawal , 1994) for discovering the maximal large set. In the approximate sub-sequence discovery algorithm, we consider the chromosome of genetic algorithm as a potential solution and employ the genetic algorithm for selecting the right solution. Two proposed algorithms work very well with large data set, therefore they satisfy the demand of the large data set of genes. Besides, we also propose a heuristic for improving the speed of solution discovery. We apply our proposed algorithms to the data of the promoters from the University of Irvine, USA and show the experiment results.