RnaSecondaryStructurePrediction에서 RNA 2차 구조 예측을 위한 알고리즘. GibbsFreeEnergy minimisation 방법이 적용되었고, 현재 가장 정확하게 작동함. MichaelZuker에 의해 만들어짐.

RNA 구조에서 GibbsFreeEnergy에 영향을 미치는 인자.

• loops
  • hairpin loop lengths
  • bulge loop lengths
  • interior loop lengths
  • multi-branch loop lengths
• base pairs
  • stacking
• single dangling nucleotides
• terminal mismatches on stems
• other secondary structure elements

NussinovRnaFoldingAlgorithm과의 가장 큰 차이점은,

• neighbouring base pairs간에 stacking contribution 고려

본 알고리즘에 사용된 GibbsFreeEnergy 계산 방법. 자세한 정보는 http://www.bioinfo.rpi.edu/~zukerm/rna/energy/

• Single base bulges : not disrupt stacking
• Longer bulges : disrupt stacking
• hairpin loop

  • a loop destabilisation energy <-- loop length

  • terminal mismatch energy <-- closing base pair and the first and last bases of the stem

DynamicProgramming기법을 사용한다. 물론 아직껏 pseudoknot은 반영되지 않는다. stacking parameter를 두개의 matrix (V, W)에 담는다.

• W(i,j) : energy of the best structure
• V(i,j) : i, j가 pair일때의 energy of the best structure

이러한 two-state 계산은 PairwiseAlignment에서의 affine gap costs방법과 유사하다.

ZukerAlgorithm의 StochasticContextFreeGrammar 버젼인 CYK and inside-outside algorithm도 유사한 ComputationalComplexity를 지닌다.