作者whyso (www)
看板CSSE
标题Re: [问题] 计算蛋白质结构等
时间Sat Jun 2 16:51:31 2007
※ 引述《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
1F：→ Arton0306:所以各胺基酸的作用方式因某些原因比单纯粒子复杂吗？ 06/02 20:52
2F：→ Arton0306:若为粒子的话 假设有abc三个粒子 由於作用力为向量式的 06/02 20:53
3F：→ Arton0306:c受的总和作力 应为a对c 及b对c的作用力之和 06/02 20:55