Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability

摘要

We study a natural probabilistic model for motif discovery that has been used to experimentally test the effectiveness of motif discovery programs. 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 = g1g2... gm is a string of m characters. Each background sequence is implanted a probabilistically generated approximate copy of G. For a probabilistically generated approximate copy b_1b_2...b_m of G, every character is probabilistically generated such that the probability for b_i ≠ g_i is at most α. It has been conjectured that multiple background sequences can help with finding faint motifs G.rnIn this paper, 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/4(1 -1/|∑|) and any constant x ≥ 8, there exist positive constants c_0,∈,δ_1 and δ_2 such that if the length ρ of motif G is at least δ_1 log n, and there are k ≥ c_0 log n input sequences, then in O(n~2 + kn) time this algorithm finds the motif with probability at least 1 -1/2~x for every G ∈ ∑~ρ -ψ_(ρ,h,∈)(∑), where ρ is the length of the motif, h is a parameter with ρ ≥ 4h ≥ δ_2 log n, and ψ_(ρ,h,∈)(∑) is a small subset of at most 2~(-Θ(∈~2h)) fraction of the sequences in ∑~ρ. The constants c_0,∈,δ_1 and δ_2 do not depend on x when x is a parameter of order O(log n). Our algorithm can take any number k sequences as input.