EXACT ALGORITHMS FOR PLANTED MOTIF CHALLENGE PROBLEMS

• DOI: 10.1142/9781860947322_0025
• Publication Date: 2007-06-08T01:58:22Z
• Authors: SANGUTHEVAR RAJAS...; SUDHA BALLA; CHUN-HSI HUANG
• Keywords: 0206 medical engineering; 02 engineering and technology

The problem of identifying meaningful patterns (i.e., motifs) from biological data has been studied extensively due to its paramount importance. Three versions of this problem have been identified in the literature. One of these three problems is the planted (l, d)-motif problem. Several instances of this problem have been posed as a challenge. Numerous algorithms have been proposed in the literature that address this challenge. Many of these algorithms fall under the category of approximation algorithms. In this paper we present algorithms for the planted (l, d)-motif problem that always find the correct answer(s). Our algorithms are very simple and are based on some ideas that are fundamentally different from the ones employed in the literature. We believe that the techniques we introduce in this paper will find independent applications. This research has been supported in part by the NSF Grants CCR-9912395 and ITR-0326155.