DNA 序列中模式发现的一种快速算法

模式发现是生物信息学的一个重要研究方向，但目前的大部分算法还不能保证获得最优的模式．文章推导了针对三个序列片段相似性关系的判据，将其作为剪枝规则，提出并实现了一种深度优先的穷举搜索算法——判据搜索算法(criterion search algorithm，CRISA)，理论分析表明，对绝大多数模式发现问题，CRISA具有多项式的计算时间复杂度和线性的空间复杂度。对仿真的和实际的生物序列数据的测试也表明，CRISA能够快速而完全地识别出序列中所有的模式，具有优于其它算法的总体评价，能够应用于实际的模式发现问题。

A fast motif finding algorithm for DNA sequence

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.