A Bayes-optimal solution to the planted motif identification problem

The planted (l, d)-motif problem asks whether a short DNA pattern hidden across multiple sequences can be recovered despite random mutations. We pose the identification problem as a Bayesian hypothesis test and derive its optimal scoring function. On the hardest standard benchmark, where approximately five spurious motifs arise by chance, the optimal score identifies the planted motif in 93% of trials; the scoring rule used by all prior algorithms achieves below 1%. An end-to-end algorithm using optimal scoring solves 19 of 20 benchmark instances with no regressions on easier cases.