Randomised sequential and parallel algorithms for efficient quorum planted motif search Online publication date: Sun, 10-Sep-2017
by Peng Xiao; Soumitra Pal; Sanguthevar Rajasekaran
International Journal of Data Mining and Bioinformatics (IJDMB), Vol. 18, No. 2, 2017
Abstract: Motifs are crucial patterns in biological sequences that have numerous applications. Motif search is an important step in obtaining meaningful patterns from biological data. However, most of the existing algorithms are deterministic and the role of randomisation in this area is still unexploited. This paper focuses on (l,d)-motif model, which is also known as Planted Motif Search (PMS) and proposes an efficient randomised algorithm, named qPMS10, to solve PMS. We utilise the most efficient PMS solver until now, named qPMS9, as a subroutine. We analyse the time complexity of both algorithms and provide a performance comparison of qPMS10 with qPMS9 on standard benchmark datasets. In addition, we offer a parallel implementation of qPMS10 and run tests using up to four processors. Both theoretical and empirical analyses demonstrate that our randomised algorithm outperforms the existing algorithms for solving PMS.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Data Mining and Bioinformatics (IJDMB):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook