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 = g ₁g₂ ⋯ 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₁b ₂ ⋯ b_m of G, every character is probabilistically generated such that the probability for b_i ≠ g_i is at most a. It has been conjectured that multiple background sequences can help with finding faint motifs G. In 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 a ≤ 1/4 (1 - 1|∑|) and any constant x ≥ 8, there exist positive constants c₀, ε, δ₁ and δ₂ such that if the length ρ of motif G is at least δ₁ log n, and there are k ≥ c₀ log n input sequences, then in O(n ²+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 ≥ δ₂ log n, and ψ_ρ,h,ε(∑) is a small subset of at most 2- ^θ(ε2h) fraction of the sequences in ∑^ρ. The constants c₀, ε, δ₁ and d₂ 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.