Research On The Algorithms And Applications For The Motif Discovery Problem

In this thesis, first introduces the background of the research of Bioinformatics, as well as the developments related in the field. One substantial model of the motif finding problem for DNA sequences in Bioinformatics is discussed in a large detail, which is called implanted (l, d)-motif model. Certain combination of l, d constitutes the problem labeled "the challenge problem". Then probability analysis on "the challenging problem" of the implanted motif model is made. According to the expectation number of existing random motifs of implanted (l,d)-motif problem, a boundary line between solvable problem and insolvable problem is revealed. Those problems that are located near the borderline are supposed to be "difficult problems".The Random Projection algorithm which is proposed by Buhler and Tompa was able to successfully solve the bulk of these "challenge problems" of the implanted (l, d)-motif model. Most details of the Random Projection algorithm are described. The improved motif finding method, based on Random Projection, reforms the building and searching of the bucket in the algorithm, and the analysis of the time complexity of the algorithm is performed. The experiment result demonstrates that running time of the improved algorithm is significant reduced and the accruary of the algorithm is guaranteed.For the loss of the accuracy of random projection algorithm while it solves the "difficult problem", an algorithm combining genetic algorithm into random projection is proposed to increase randomness and improve the global searching ability of the random projection algorithm. After the projection strategy, genetic operators on the population in which individuals are composed of planted buckets are used to optimize the solutions of the problem. Experimental results show that the motif finding algorithm combining genetic algorithm improves the overall correct rate than random projection.