Discovering almost any hidden motif from multiple sequences

We study a natural probabilistic model for motif discovery. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet ∑. A motif G = g₁g ₂ ⋯ g_m is a string of m characters. Each background sequence is implanted with a probabilistically generated approximate copy of G. For a probabilistically generated approximate copy b₁b₂ ⋯ bm of G, every character is probabilistically generated such that the probability for b_i ≠ g_i is at most α. In this article, we develop an efficient algorithm that can discover a hidden motif from a set of sequences for any alphabet ∑ with |∑| ≥ 2 and is applicable to DNA motif discovery. We prove that for α < 1/8 (1 - 1/|∑| ), there exist positive constants c₀, ε, and δ₂ such that if there are at least c₀ logn input sequences, then in O( n²/h (log n)^O(1)) time this algorithm finds the motif with probability at least 3/4 for every G ε ∑^p - ψ_p,h,ε (∑), where n the length of longest sequences, p is the length of the motif, h is a parameter with p ≥ 4h ≥ δ₂ log n, and εp,h,ε (∑) is a small subset of at most 2-Θ(ε²h) fraction of the sequences in ∑^p .