2026-09-21T22:57:00Z https://meral.edu.mm/oai

oai:meral.edu.mm:recid/2349 2021-12-13T03:00:33Z 1582963390870:1582967549708 user-uy

AN EFFICIENT EXACT SOLUTION TO THE (L, D)-PLANTED MOTIF PROBLEM Sia, Maria Clara Isabel D. Nabos, Julieta Q. Fernandez, Proceso L. DNA motif finding is widely recognized as a difficult problem in computational biology and computer science. Because of the usual large search space involved, exact solutions typically require a significant amount of execution time before discovering a motif of length d that occurs in each sequence Si from an input set {Sl, ...,Sf} of sequences, allowing for at most d substitutions. In this paper, we propose a novel algorithm that operates on a compact bit-based representation of the search space and takes advantage of distance-related patterns in this representation in order to compute the exact solution for any arbitrary problem instance up to l, d =6. A Java implementation-run on synthetic datasets for various challenge instances of the (l, d) motif finding problem-shows the proposed algorithm to be highly competitive against PMS8 and qPMS9, two current state-of the- art exact motif search algorithms. The proposed algorithm works extremely well for problems involving short motifs, outperforming the current best algorithm for the challenge problem instances (13,4) and (IS,S) with a runtime reduction of at least 50% and 20% respectively for these instances, while ranking second to qPMS9 for test instances involving l =16 and l =17. 2015 http://hdl.handle.net/20.500.12678/0000002349 https://meral.edu.mm/records/2349