IDEAS home Printed from https://ideas.repec.org/a/apa/ijtess/2017p124-132.html
   My bibliography  Save this article

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

Author

Listed:
  • MARK JOSEPH D. RONQUILLO

    (Ateneo de Manila University, Quezon City, Philippines)

  • PROCESO L. FERNANDEZ

    (Ateneo de Manila University, Quezon City, Philippines)

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.

Suggested Citation

  • Mark Joseph D. Ronquillo & Proceso L. Fernandez, 2017. "EMS-GT2: An Improved Exact Solution for the (l, d)-Planted Motif Problem," International Journal of Technology and Engineering Studies, PROF.IR.DR.Mohid Jailani Mohd Nor, vol. 3(3), pages 124-132.
    • Handle: RePEc:apa:ijtess:2017:p:124-132
    DOI: 10.20469/ijtes.3.40005-3
    as

    Download full text from publisher

    File URL: https://kkgpublications.com/technology-engineering-studies-volume-3-issue-3/
    Download Restriction: no
    File URL: https://kkgpublications.com/wp-content/uploads/2018/09/ijtes.3.40005-3.pdf
    Download Restriction: no
    File URL: https://libkey.io/10.20469/ijtes.3.40005-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hieu Dinh & Sanguthevar Rajasekaran & Jaime Davila, 2012. "qPMS7: A Fast Algorithm for Finding (ℓ, d)-Motifs in DNA and Protein Sequences," PLOS ONE, Public Library of Science, vol. 7(7), pages 1-8, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hieu Dinh & Sanguthevar Rajasekaran, 2013. "PMS: A Panoptic Motif Search Tool," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-7, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:apa:ijtess:2017:p:124-132. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: PROF.IR.DR.Mohid Jailani Mohd Nor (email available below). General contact details of provider: https://kkgpublications.com/technology/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.