HMMF: An Hidden Markov Model Based Approach for Motif Finding

Transcriptional factor binding site (TFBS) motifs on DNA genomes play important functional roles in gene expression and regulation. Accurately identifying the motifs is thus an important problem in bioinformatics. However, exhaustively enumerating all possible locations for a motif in a set of sequences is computationally intractable. Many heuristic or approximation algorithms and machine learning based approaches have been developed for this problem. In this paper, we develop a novel approach that can efficiently explore all possible locations of TFBS motifs in a set of sequences with high accuracy. Our approach constructs an ensemble of k Hidden Markov Models (HMM) through local alignments of two sequences in the set and then progressively aligns each HMM in the ensemble to other sequences in the set and update the parameters of the k HMMs. Our experimental results showed that our approach could achieve higher accuracy with satisfying efficiency than previous state-of-art approaches.