Abstract

Understanding the mechanisms that regulate gene expression is a major challenge in computational biology. An important part of solution in understanding this problem is to identify the binding sites in DNA for transcription factors known as motifs. Discovery of motifs in unaligned sequences is a fundamental problem in computational biology. Motif search using HMM and gibbs sampling have been shown to be very effective in finding regulatory motifs. We recently proposed a novel motif finding algorithm [1] that models, within a general framework, binding elements in terms of a variable number of motifs that are separated by spacers of varying lengths. The model is very effective for motif finding, but is computationally very expensive. In this paper, we propose a graphtheoretic framework for efficient computation of our HMM model for motif finding. The proposed graph model is very flexible, easy to use and is shown …