EMS-GT2: An Improved Exact Solution for the (l, d)-Planted Motif Problem

Mark Joseph D. Ronquillo and Proceso L. Fernandez
Additional contact information
Mark Joseph D. Ronquillo: Ateneo de Manila University, Quezon City, Philippines
Proceso L. Fernandez: Ateneo de Manila University, Quezon City, Philippines

International Journal of Technology and Engineering Studies, 2017, vol. 3, issue 3, 124-132

Abstract: Finding DNA motifs is a widely studied area in the field of Computational Biology. Motifs signify different information that is useful for biologists. There are several variations of the motif finding problem, and one of these is called the (l, d)-motif search or Planted Motif Search problem (PMS). In this paper, we propose the EMS-GT2 algorithm, an extension of the Exact Motif Search-Generate and Test (EMS- GT) which is an exact enumerative algorithm for PMS. In EMS-GT2, we incorporated a new speedup technique that is based on an important property that we have discovered, which we prove in this paper, and which has enabled a more efficient block-processing of candidate motifs. Our C++ implementation of EMS-GT2 running on synthetic data for several PMS challenge instances demonstrates that it is competitive with both the EMS-GT and qPMS9, the two current best exact solutions for PMS. In particular, EMS-GT2 is able to reduce the run-times of EMS-GT by 20.3%, 15.8% and 22.6% for the (l, d) challenge instances (13, 4), (15, 5) and (17, 6) respectively. It also outperforms qPMS9, having runtime reductions of 91.6%, 79.3%, 82.0%, 59.4% and 9.7% for the (9, 2), (11, 3), (13, 4), (15, 5) and (17, 6) synthetic challenge instances respectively.

Keywords: Planted (l; d)-Motif Problem; Bit-Based; Exact Enumerative Algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://kkgpublications.com/technology-engineering-studies-volume-3-issue-3/ (application/pdf)
https://kkgpublications.com/wp-content/uploads/2018/09/ijtes.3.40005-3.pdf (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:apa:ijtess:2017:p:124-132

DOI: 10.20469/ijtes.3.40005-3

Access Statistics for this article

International Journal of Technology and Engineering Studies is currently edited by PROF.IR.DR.Mohid Jailani Mohd Nor

More articles in International Journal of Technology and Engineering Studies from PROF.IR.DR.Mohid Jailani Mohd Nor Calle Alarcon 66, Sant Adrian De Besos 08930, Barcelona Spain.
Bibliographic data for series maintained by PROF.IR.DR.Mohid Jailani Mohd Nor ().