Research On Motif Finding Algorithm Based On Gibbs Sampling

The motifs in the biological sequences play an important role in gene transfer, so motif finding in biological sequences is of great significance and theoretical value. Motif finding problem has become one of hot issues in the field of Bioinformatics.At present, there are many effective algorithms have been used to solve the problem of motif finding, such as YMF, MEME and random projection algorithm. In 1993, Chip Lawrence and his colleagues firstly used gibbs sampling algorithm to find the motif in the DNA sequences. Due to the sensitivity and fast convergence, the gibbs sampling algorithm become the one of the most effective methods for motif finding problem.This paper firstly describes the definition of the motif finding problem, and analyze the commonly used motif models. Then several algorithms used to find motifs based on these different motif models have been analyzed and compared. Some of the traditional algorithms are based on the exhaustive search and cost a lot of time, and some of them is easy to fall into local optimum and can not find the global optimum. So based on the traditional Gibbs sampling algorithm, a new improved algorithm has been developed to tackle motif finding problem. Based on the consideration that the positions within a motif are not completely independent and there exists interdependency among positions in some motifs, we introduce high-order background model. And we use the idea of random projection, and replace the random strategy with random projection strategy to construct the initial training set. Finally, we effectively enhance the convergence of the iterative processes and the accuracy of motif finding. The results of experiments on multiple sets data show great improvement in accuracy of finding true motifs.