Performance and Analysis of Modified Voting Algorithm for Planted Motif Search

摘要

We consider the planted (l, d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s_1, s_2, …, s_n} with maximum Hamming distance, d, around the similar substring. In this paper, we present an experimental comparison between voting algorithm and its modification for planted motif on simulated data from (9, d) to (15, d) in case of challenging instances. The experimental results show that the modified voting algorithm is not better than voting algorithm as theoretically suggested. The results show that the running of voting algorithm is faster than modified voting algorithm in all the cases studied. We also determine, experimentally, the number of sequences that are required to make the modified voting algorithm faster than voting algorithm.