[問題] 計算蛋白質結構等

[Arton0306 (烏索普阿阿阿~~~)]

在計算生物學中
很多NPC NPHard的問題
像給一蛋白質序列和各鍵結之間的能量大小等
要計算出其3D立體結構 使其具最小自由能
像這個就是NPHard

另外物理系的他們也有研究用simulation的方法
把分子、原子等的物理之間的關系輸入進去
用電腦去模擬
關於模擬的方式其時間複雜度是怎麼算呢？
若把蛋白質看成一粒粒粒子
或是看成一單位一單位的胺基酸
那麼把各胺基酸之間的作用關系等輸入
每當新增一個胺基酸時
也只是多算這個胺基酸和原有胺基酸的作用關系
感覺起來似乎是O(n^2)
但這樣就和NPHard有衝突了

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.195.22.165
推 FRAXIS:模擬 跟去解決 是不一樣的吧
推 Arton0306:那如果說模擬的結果和用algo算出來答案一樣呢？
推 Arton0306:或者說simulation也能看成是一種algo
→ Arton0306:這樣不就具有O(n^2)的algo了 所以覺得怪怪的
推 seagal:simu只能得出近似解 某些情況下 近似解逼近正解或等於
→ seagal:333篇剛好有稍微提到一點相關的討論
→ Arton0306:感謝感謝