Subtle Motif Discovery Algorithms

Finding motifs is a significant computational problem in bioinformatics, many models and algorithms have been proposed to solve this problem. By reason of the complexity of biologic sequence data; there exist lots of subtle motifs which are much more difficult to be found than strong signals.Up to now, the planted (l, d) motif problem and the extended planted (l, d) motif problem are two suitable models for finding subtle motifs; So that the author mainly studies these two problem models. Besides, the author generalizes and analyzes the methods and strategies of motif discovery and the motif model as well as their advantages and disadvantages. Based on the above work, the author further assays some main present subtle motif discovery algorithms through experiments.Aiming at subtle motif discovery problem, the author introduces the UPNT (Uniform Projection with Neighbourhood Thresholding) algorithm, which based on, two efficient strategies, Uniform Projection and Neighbourhood-based Thresholding. In UPNT algorithm, the policy of uniform projection leads to less projections, while the strategy of refining the buckets after AGGREGATION results in great abatement of the number of buckets to be refined. The author further demonstrates the test results and analyses of UPNT algorithm and other algorithms experimented on two synthetic (l, d) datasets with unbiased as well as biased background, while the results demonstrate: UPNT algorithm shows superior to Random Projection,AGGREGATION and Uniform Projection in the synthetic performance of success rate and average running time, therefore carries greater applicability.By reason that there exist many dyad motifs with gaps, in which one submotif may be subtle but statistically strong for their unity. The author introduces an exact algorithm DMDB (Dyad Motif Discovery based on Box-Links), which is based on the enumeration of Box-Links to score and choose dyad motif from the candidate motifs. The author also verifies DMDB's efficiency by way of experiments.Finally, the author summarizes the motif discovery problems and provides discussion on some unresolved problems and development trend in this field.