A fast motif finding algorithm for DNA sequence
DNA 序列中模式发现的一种快速算法

Motif finding is an important research field in bioinformatics. Many algorithms on motif finding have been developed at present, but among these algorithms only few can find the correct motif surely, such as MITRA. In this paper, a new exhaust search algorithm named CRISA (criterion search algorithm) is proved. It can accomplish the exhaust search with less computation resource. This target is achieved based on the criterion describing the relations between three similar segments deduced in this paper. Using this criterion as pruning rule, CRISA can reduce the search space effectively in the deeply first search process. Theoretical analysis on CRISA is done in this paper, and the results show that under some rather loose conditions, the computational complexity of CRISA is a polynomial function of the length and the number of the input sequences. Then, some tests using simulated and biological data have been done and the results show that it is more efficient than other exhaust search algorithms obviously, and its search speed is even faster than that of many non-exhaust search algorithms.