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_1g _2 ? 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_1b_2 ? 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_0, ε, and δ_2 such that if there are at least c0 logn input sequences, then in O(n~2/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 ≥ δ_2 log n, and εp,h,ε (∑) is a small subset of at most 2-Θ(ε~2h) fraction of the sequences in ∑p.