What Are The Brute Force Based Algorithms For Dna Motif Finding

Question

[User 4000]

what are the Brute Force based algorithms for DNA Motif Finding ? and is Brute Force method for DNA motif finding widely used?

[Steve Lianoglou]

Can you give us an example of an algorithm that you consider to be "brute force" vs. one that isn't? I don't think it's clear what you are looking for.

[User 4000]

I'm looking for algorithms that have been developed for motif finding based on Brute force search method.For example is PMS1 algorithm based on Brute force.i actually don't know much details about them.

Answer 1

[Martin A Hansen]

scan_for_matches is based on brute force backtracking.

[User 4000]

Can you give me an example?

Answer 2

[SES]

This new paper describing a software called CodingMotif may be helpful. Though it only applies to coding regions.

Answer 3

[Fabian Bull]

If your understanding of Brute Force is: check for every possiblity.

Then there can be no algorithm with decent model assumptions. The number of possible motif combinations is just too high.

Because of the high number you generally use statistical sampling to infer properties of the motifs. The algorithms used for this approach are:

EM, Gibbs Sampling and Metropolis Hastings

Programs which use these are:

MEME or Gibbs Motif Sampler

Answer 4

[Malachi Griffith]

The cisRED (cis-regulatory element database) project uses a combination of Consensus, MEME, and GibbsMotifSampler (another one here: MotifSampler).

Answer 5

[razor]

Two articles that might help:

• A survey of DNA motif finding algorithms

• Efficient exact motif discovery