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를 지닌다.

ZukerAlgorithm (last edited 2011-08-03 11:00:39 by localhost)

web biohackers.net