Difference between revisions of "Lecture 11"
Jump to navigation
Jump to search
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | <div style="padding: 5px; background: #FF4560; border:solid 2px #000000;"> | ||
| + | '''Update Warning!''' | ||
| + | This page has not been revised yet for the 2007 Fall term. Some of the slides may be reused, but please consider the page as a whole out of date as long as this warning appears here. | ||
| + | </div> | ||
| + | | ||
| + | |||
| + | | ||
| + | |||
| + | |||
__NOTOC__ | __NOTOC__ | ||
<small>[[Lecture_10|(Previous lecture)]] ... [[Lecture_12|(Next lecture)]]</small> | <small>[[Lecture_10|(Previous lecture)]] ... [[Lecture_12|(Next lecture)]]</small> | ||
| Line 30: | Line 39: | ||
======Slide 004====== | ======Slide 004====== | ||
[[Image:L11_s004.jpg|frame|none|Lecture 11, Slide 004<br> | [[Image:L11_s004.jpg|frame|none|Lecture 11, Slide 004<br> | ||
| + | A toy observation on an optimization problem of similar magnitude as the random folding of a protein... | ||
| + | ]] | ||
| − | |||
======Slide 005====== | ======Slide 005====== | ||
[[Image:L11_s005.jpg|frame|none|Lecture 11, Slide 005<br> | [[Image:L11_s005.jpg|frame|none|Lecture 11, Slide 005<br> | ||
| Line 86: | Line 96: | ||
======Slide 018====== | ======Slide 018====== | ||
[[Image:L11_s018.jpg|frame|none|Lecture 11, Slide 018<br> | [[Image:L11_s018.jpg|frame|none|Lecture 11, Slide 018<br> | ||
| + | Non-polynomial time-complexity problems are considered intractable, since even as the problem size ''''n'''' grows only modestly, the time requirements grow beyond all bounds and reasonable resources. A 1,000 element problem of ''O''(2<sup>''n''</sup>) complexity takes the age of the universe to compute. | ||
| + | ]] | ||
| − | |||
======Slide 019====== | ======Slide 019====== | ||
[[Image:L11_s019.jpg|frame|none|Lecture 11, Slide 019<br> | [[Image:L11_s019.jpg|frame|none|Lecture 11, Slide 019<br> | ||
| Line 110: | Line 121: | ||
======Slide 024====== | ======Slide 024====== | ||
[[Image:L11_s024.jpg|frame|none|Lecture 11, Slide 024<br> | [[Image:L11_s024.jpg|frame|none|Lecture 11, Slide 024<br> | ||
| + | Simulated annealing allows a system to be computationally moved out of situations where it is trapped in local minima, and to proceed towards a global minimum on a rough search landscape. | ||
| + | ]] | ||
| − | |||
======Slide 025====== | ======Slide 025====== | ||
[[Image:L11_s025.jpg|frame|none|Lecture 11, Slide 025<br> | [[Image:L11_s025.jpg|frame|none|Lecture 11, Slide 025<br> | ||
| + | A simulated annealing strategy (in pseudocode). | ||
| + | ]] | ||
| − | |||
======Slide 026====== | ======Slide 026====== | ||
[[Image:L11_s026.jpg|frame|none|Lecture 11, Slide 026<br> | [[Image:L11_s026.jpg|frame|none|Lecture 11, Slide 026<br> | ||
| + | Many believe that genetic algorithms - albeit interesting - rarely outperform simulated annealing. | ||
| + | ]] | ||
| − | |||
======Slide 027====== | ======Slide 027====== | ||
[[Image:L11_s027.jpg|frame|none|Lecture 11, Slide 027<br> | [[Image:L11_s027.jpg|frame|none|Lecture 11, Slide 027<br> | ||
| + | Natural proteins of course have evolved under the constraint of foldability. They may have avoided mutations that would expose them to the requirements of full, combinatorial optimization of their 3-D structure. | ||
| + | ]] | ||
| − | |||
======Slide 028====== | ======Slide 028====== | ||
[[Image:L11_s028.jpg|frame|none|Lecture 11, Slide 028<br> | [[Image:L11_s028.jpg|frame|none|Lecture 11, Slide 028<br> | ||
Latest revision as of 15:27, 1 September 2007
Update Warning! This page has not been revised yet for the 2007 Fall term. Some of the slides may be reused, but please consider the page as a whole out of date as long as this warning appears here.
(Previous lecture) ... (Next lecture)
Protein Structure Prediction
...
Add:
- Summary points
- Exercises
- Further reading
Lecture Slides
Slide 001
Lecture 11, Slide 001
Slide 002
Lecture 11, Slide 002
Slide 003
Lecture 11, Slide 003
The observation became famously known as "Levinthal's Paradox", that neither random search nor the postulation of folding pathways can explain how a discrete structure can self-organize, given in a combinatorially large search space. But real proteins do just fine, thank you.
The observation became famously known as "Levinthal's Paradox", that neither random search nor the postulation of folding pathways can explain how a discrete structure can self-organize, given in a combinatorially large search space. But real proteins do just fine, thank you.
Slide 004
Lecture 11, Slide 004
A toy observation on an optimization problem of similar magnitude as the random folding of a protein...
A toy observation on an optimization problem of similar magnitude as the random folding of a protein...
Slide 005
Lecture 11, Slide 005
Slide 006
Lecture 11, Slide 006
Slide 007
Lecture 11, Slide 007
Slide 008
Lecture 11, Slide 008
Slide 009
Lecture 11, Slide 009
Slide 010
Lecture 11, Slide 010
Slide 011
Lecture 11, Slide 011
Slide 012
Lecture 11, Slide 012
Slide 013
Lecture 11, Slide 013
Slide 014
Lecture 11, Slide 014
Slide 015
Lecture 11, Slide 015
Slide 016
Lecture 11, Slide 016
Slide 017
Lecture 11, Slide 017
Slide 018
Lecture 11, Slide 018
Non-polynomial time-complexity problems are considered intractable, since even as the problem size 'n' grows only modestly, the time requirements grow beyond all bounds and reasonable resources. A 1,000 element problem of O(2n) complexity takes the age of the universe to compute.
Non-polynomial time-complexity problems are considered intractable, since even as the problem size 'n' grows only modestly, the time requirements grow beyond all bounds and reasonable resources. A 1,000 element problem of O(2n) complexity takes the age of the universe to compute.
Slide 019
Lecture 11, Slide 019
Slide 020
Lecture 11, Slide 020
Slide 021
Lecture 11, Slide 021
Slide 022
Lecture 11, Slide 022
Slide 023
Lecture 11, Slide 023
Slide 024
Lecture 11, Slide 024
Simulated annealing allows a system to be computationally moved out of situations where it is trapped in local minima, and to proceed towards a global minimum on a rough search landscape.
Simulated annealing allows a system to be computationally moved out of situations where it is trapped in local minima, and to proceed towards a global minimum on a rough search landscape.
Slide 025
Lecture 11, Slide 025
A simulated annealing strategy (in pseudocode).
A simulated annealing strategy (in pseudocode).
Slide 026
Lecture 11, Slide 026
Many believe that genetic algorithms - albeit interesting - rarely outperform simulated annealing.
Many believe that genetic algorithms - albeit interesting - rarely outperform simulated annealing.
Slide 027
Lecture 11, Slide 027
Natural proteins of course have evolved under the constraint of foldability. They may have avoided mutations that would expose them to the requirements of full, combinatorial optimization of their 3-D structure.
Natural proteins of course have evolved under the constraint of foldability. They may have avoided mutations that would expose them to the requirements of full, combinatorial optimization of their 3-D structure.
Slide 028
Lecture 11, Slide 028
Slide 029
Lecture 11, Slide 029
Slide 030
Lecture 11, Slide 030
Slide 031
Lecture 11, Slide 031
Slide 032
Lecture 11, Slide 032
Slide 033
Lecture 11, Slide 033
Slide 034
Lecture 11, Slide 034
Slide 035
Lecture 11, Slide 035
Slide 036
Lecture 11, Slide 036
Slide 037
Lecture 11, Slide 037
Slide 038
Lecture 11, Slide 038
