Why can't brute force be used?

  • 2
  • Question
  • Updated 9 years ago
  • Answered
Why can't a brute force algorithm be used for solving? There are only a few million possibilities (if I did my math right) and assuming they only take a fraction of a second to solve, that's one RNA solved for every possible arrangement in only a few days. Why do we need humans?
Photo of Aviel Menter

Aviel Menter

  • 3 Posts
  • 0 Reply Likes
  • curious

Posted 9 years ago

  • 2
Photo of Adrien Treuille

Adrien Treuille, Alum

  • 243 Posts
  • 33 Reply Likes
Aviel, glad you asked! Brute force algorithms could indeed successfully solve the smaller puzzles on EteRNA, but the issue is that in principle, the brute force approach quickly becomes infeasible as the puzzle size increases. For this reason, biologists have sought algorithms that solve the RNA design problem without resorting to brute force. Playing EteRNA challenges players to find such heuristic strategies, some of which may prove to be better than those known to biologists.

More generally, the heart of EteRNA is The Lab, where player designs are scored based on real experimental synthesis and validation. As we hypothesize new criteria for successful synthesis, we will need to develop new strategies which satisfy these criteria. There has never been a game quite like EteRNA before. It's going to be an exciting ride, and we're just beginning!
Photo of Christopher VanLang

Christopher VanLang, Alum

  • 30 Posts
  • 9 Reply Likes
I think a major limitation in computational approaches is that the energetic parameters aren't up to par. While some of the energetics are known as shown in the game, some elements like loops and bulges are often neglected or unknown. As Adrien mentioned, as the puzzles scale up, the brute force methods suffer from both computational limitations and inaccuracies in their assumptions.

To make up for the lack of good parameters, one could use molecular dynamics (see folding@home) but those methods are still unable to look at even the smaller sized RNAs.

Perhaps a machine learning algorithm approach could be used to parse the data and determine elements that make good RNA. It does requires some intuitive guesses on what those elements are. However, an alternative strategy is to learn by building and that is essentially what EteRNA is.
Photo of Paul Murray

Paul Murray

  • 3 Posts
  • 0 Reply Likes
Oooh, I think your math is definitely off. Each base can be one of four values. Ten bases gives you about a million possibilities. Twenty a trillion. Thirty a ... a kajillion. Brute force very, very quickly becomes infeasible.
Photo of JRStern

JRStern

  • 42 Posts
  • 2 Reply Likes
Completely blind brute force is impractical, as Paul shows, but implementing the kinds of algorithms we're all doing here is feasible.

I'm not clear on just what it is that the lab validates, that a given solution truly folds the way the game shows it? Is it that simple? Thanks.
Photo of Adrien Treuille

Adrien Treuille, Alum

  • 243 Posts
  • 33 Reply Likes
JRStern. Those are great points, and yes: that is what the lab validates. And the exciting thing is that we know that RNAs do not fold in practice the way they do in the program--which is our best model--so we want to discover principles that reliably form sequences which do fold properly.