An improved voting algorithm for planted (1,d) motif search

作者：Xu Yun^*; Yang Jiaoyun; Zhao Yuzhong; Shang Yi

来源：Information Sciences, 2013, 237: 305-312.

DOI：10.1016/j.ins.2013.03.023

• Planted motif search
• Exact algorithm
• Time and space complexity
• Challenging instances

The planted motif search problem is a classical problem in bioinformatics that seeks to identify meaningful patterns in biological sequences. As an NP-complete problem, current algorithms focus on improving the average time complexity and solving challenging instances within an acceptable time. In this paper, we propose a new exact algorithm CVoting that improves the state-of-the-art Voting algorithm. CVoting uses a new hash technique to reduce the space complexity to O(mn + N(I,d)) and a new pruning technique to reduce the average time complexity to O(m2 nN(1, d)(1,). Experimental results show that CVoting outperforms competing algorithms, including PMS1, RISOTTO, Voting and Pmsprune, in both space and time: up to an order of magnitude faster and using less memory in solving challenging instances. The software of the proposed algorithm is publicly available at http://staff.ustc.edu.cnixuyunimotif.

• 出版日期2013-7-10
• 单位中国科学技术大学