Answers.Body: <p>Protein folding problem can be viewed as a minimization problem. One can use <a href="https://en.wikipedia.org/wiki/Quantum_annealing" rel="noreferrer">quantum annealing</a> to perform the minimization. Running this on quantum computers would improve the performance since they can perform the tunneling directly.</p>
  
  <p>In fact, quantum annealing was <a href="https://dx.doi.org/10.1038/srep00571" rel="noreferrer">used</a> (<a href="http://blogs.nature.com/news/2012/08/d-wave-quantum-computer-solves-protein-folding-problem.html" rel="noreferrer">blog post</a>) for lattice protein folding on the the D-Wave quantum computer (128 qubits). But this was an extremely simplified model, with only 40 discrete states.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-08T17:54:28.040Z
Answers.LastActivityDate: 2017-06-08T17:54:28.040Z
Answers.UserDisplayName: Iakov Davydov
Answers.Body: <p>I would expect that without any further insights into protein folding, a quantum method would look fairly similar to existing methods, but might have a bit more capability of exploring multiple states at the same time (without multitasking).</p>
  <p>Here's the approach used by <a href="http://boinc.bakerlab.org/rosetta/rah_graphics.php" rel="nofollow noreferrer">Rosetta</a>, which is used in both the <a href="http://boinc.bakerlab.org/" rel="nofollow noreferrer">Rosetta@home</a> distributed computing project, and the <a href="http://fold.it/portal/" rel="nofollow noreferrer">foldit</a> distributed gaming project:</p>
  <blockquote>
  <p>Rosetta's strategy for finding low energy shapes looks like this:</p>
  <ol>
  <li>Start with a fully unfolded chain (like a metal chain with its ends pulled).</li>
  <li>Move a part of the chain to create a new shape.</li>
  <li>Calculate the energy of the new shape.</li>
  <li>Accept or reject the move depending on the change in energy.</li>
  <li>Repeat 2 through 4 until every part of the chain has been moved a lot of times.</li>
  </ol>
  <p>We call this a trajectory. The end result of a trajectory is a predicted structure.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-08T22:24:52.593Z
Answers.Text: wow that's surprising. I would have expected the protein to start folding as soon as one end of it is able to, which is probably the first end to leave the ribosome. The last amino acid probably hasn't even been attached yet, let alone available for moving and calculating the energy :)
Answers.UserDisplayName: J.J
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-09T01:57:32.613Z
Answers.Text: That does happen to some degree, but the Rosetta [computer] model doesn't do this. A whole bunch of odd things happen with protein folding. For example, there are chaperone proteins that encourage folding in a particular fashion to get through low-energy humps to reach a higher energy state. The foldit researchers have found a way to model chaperones using a technique called "humans".
Answers.UserDisplayName: gringer
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-08T15:00:23.893Z
Answers.LastActivityDate: 2017-06-08T15:00:23.893Z
Answers.LastEditDate: 2020-06-18T08:30:41.743Z
Answers.UserDisplayName: gringer
Body: <p>It's supposed that quantum computers could help to find the native state of all human DNA proteins.</p>
  
  <p>Does anyone know how to formulate the protein folding problem into a decision problem solvable either by <a href="https://en.wikipedia.org/wiki/Quantum_annealing" rel="nofollow noreferrer">quantum annealers</a> or <a href="https://en.wikipedia.org/wiki/Quantum_Turing_machine" rel="nofollow noreferrer">universal quantum computers</a>?</p>
  
  <p>It would also be interesting to know, how to model a decision problem for classical computers, like <a href="http://folding.stanford.edu/" rel="nofollow noreferrer">Folding@Home</a>.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-08T03:32:10.457Z
Comments.Text: Welcome to Bioinformatics.SE! I'm afraid in its current state this question is very broad and may not be a good fit for this site in its current state.
Comments.UserDisplayName: Daniel Standage
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-08T03:40:48.937Z
Comments.Text: @DanielStandage thanks! ooo! ok understand! hopefully someone helps, since there is a big curiosity about this :D
Comments.UserDisplayName: ncomputers
Tags: <proteins><computation>
Title: Protein folding problem model for quantum computers?
ThreadText: # Protein folding problem model for quantum computers?
  
  (Asked by: username_0 on 2017-06-08)
  
  It's supposed that quantum computers could help to find the native state of all human DNA proteins.
  
  Does anyone know how to formulate the protein folding problem into a decision problem solvable either by [quantum annealers](https://en.wikipedia.org/wiki/Quantum_annealing) or [universal quantum computers](https://en.wikipedia.org/wiki/Quantum_Turing_machine)?
  
  It would also be interesting to know, how to model a decision problem for classical computers, like [Folding@Home](http://folding.stanford.edu/).
  
  **Tags:** proteins, computation
  
  > **Comments:**
  > **username_1**: Welcome to Bioinformatics.SE! I'm afraid in its current state this question is very broad and may not be a good fit for this site in its current state.  
  > **username_0**: @username_1 thanks! ooo! ok understand! hopefully someone helps, since there is a big curiosity about this :D  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2017-06-08. Score: 5
  
  Protein folding problem can be viewed as a minimization problem. One can use [quantum annealing](https://en.wikipedia.org/wiki/Quantum_annealing) to perform the minimization. Running this on quantum computers would improve the performance since they can perform the tunneling directly.
  
  In fact, quantum annealing was [used](https://dx.doi.org/10.1038/srep00571) ([blog post](http://blogs.nature.com/news/2012/08/d-wave-quantum-computer-solves-protein-folding-problem.html)) for lattice protein folding on the the D-Wave quantum computer (128 qubits). But this was an extremely simplified model, with only 40 discrete states.
  
  
  ---
  
  ### Answer by username_3 on 2017-06-08. Score: 1
  
  I would expect that without any further insights into protein folding, a quantum method would look fairly similar to existing methods, but might have a bit more capability of exploring multiple states at the same time (without multitasking).
  
  Here's the approach used by [Rosetta](http://boinc.bakerlab.org/rosetta/rah_graphics.php), which is used in both the [Rosetta@home](http://boinc.bakerlab.org/) distributed computing project, and the [foldit](http://fold.it/portal/) distributed gaming project:
  
  > Rosetta's strategy for finding low energy shapes looks like this:
  >
  > 1. Start with a fully unfolded chain (like a metal chain with its ends pulled).
  > 2. Move a part of the chain to create a new shape.
  > 3. Calculate the energy of the new shape.
  > 4. Accept or reject the move depending on the change in energy.
  > 5. Repeat 2 through 4 until every part of the chain has been moved a lot of times.
  >
  > We call this a trajectory. The end result of a trajectory is a predicted structure.
  
  > **Comments:**
  > **username_4**: wow that's surprising. I would have expected the protein to start folding as soon as one end of it is able to, which is probably the first end to leave the ribosome. The last amino acid probably hasn't even been attached yet, let alone available for moving and calculating the energy :)  
  > **username_3**: That does happen to some degree, but the Rosetta [computer] model doesn't do this. A whole bunch of odd things happen with protein folding. For example, there are chaperone proteins that encourage folding in a particular fashion to get through low-energy humps to reach a higher energy state. The foldit researchers have found a way to model chaperones using a technique called "humans".  
  
  ---
  
  