Re: [問題] 計算蛋白質結構等
※ 引述《Arton0306 (烏索普阿阿阿~~~)》之銘言：
: 在計算生物學中
: 很多NPC NPHard的問題
: 像給一蛋白質序列和各鍵結之間的能量大小等
: 要計算出其3D立體結構 使其具最小自由能
: 像這個就是NPHard
: 另外物理系的他們也有研究用simulation的方法
: 把分子、原子等的物理之間的關系輸入進去
: 用電腦去模擬
: 關於模擬的方式其時間複雜度是怎麼算呢？
: 若把蛋白質看成一粒粒粒子
: 或是看成一單位一單位的胺基酸
: 那麼把各胺基酸之間的作用關系等輸入
: 每當新增一個胺基酸時
: 也只是多算這個胺基酸和原有胺基酸的作用關系
^^^^^^^^^^^^^^^^^^^^^^^^
這種計算方式叫做greedy algorithm，
通常只有一些簡單的問題才能夠用greedy的方式來看待。
: 感覺起來似乎是O(n^2)
: 但這樣就和NPHard有衝突了
假設原來的胺基酸是 LRVK，新增一個胺基酸 G
由於蛋白質是三維結構，跟這個新的G的互動方式不會只是(LRVK,G)這樣的線性關係。
也還需要考慮 (L,G),(R,G),(V,G),(K,G),... ,(LRV,G), (RVK,G),...等互動。
任何模擬系統都差不多是這樣，新加入一個東西時，
要考慮的是這個東西和原先"所有"東西的互動，所以用暴力法來看的話，
計算複雜度至少是是 2^n，而不是2^n。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.222.123
→
06/02 20:52, , 1F
06/02 20:52, 1F
→
06/02 20:53, , 2F
06/02 20:53, 2F
→
06/02 20:55, , 3F
06/02 20:55, 3F
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
