[PerlChina] Re: DNA,DG值。

我是这样想的:
你的问题可以转化成这样一个图论问题： n个顶点的有权无向图G，找出最大子图H，满足条件：子图中的任意两点间有边，且边的权重大于一个阈值p。
我的思路是这样的：
先找出所有权重大于p的边，这些边和对应顶点组成的子图为L。容易想到H是L的子图。
然后在L中去掉不和L中任意其他点有边的顶点。剩下的图就是H。

程序我就不写了...

On 7月13日, 下午9时11分, jie liu <liujie....@gmail.com> wrote:
> 谢谢两位的回复，确实，通过这个反例证明我那个方法不能找到最优解。我请教了我的一个同学，他叫我用 图论
> 来解决这个问题：建立这样一个图模型：该图含有400个顶点，代表不同的DNA；含有若干边，边代表两DNA可以发生杂交（dG<1）。用矩阵描述这个图。然后 利用matlab
> bioinformational tool中的graphconncomp()（http://www.mathworks.com/help/toolbox/bioinfo/ref/graphconncomp.html
> ）找若弱连通图。我对他这个方法的理解是这样的：孤立的点（一种弱连通图），一定是可以放进这个子集的；同时必然还存在一些其他的弱连通图中的顶点是可以放进这 个子集的。如果matlab绘出图来，我倒是可以根据边的关系选出符合条件的点来，但是毕竟这是人工找出的，不是程序运算出的。关于用图论解决这个问题，大家有 好的想法吗？
>
> 2011/7/13 zjf <microsoft_w...@126.com>
>
>
>
>
>
>
>
>
>
>
>
> > 在 2011-07-12 20:19:25，"jie liu" <liujie....@gmail.com> 写道：
>
> > 大家好！
>
> > 我这有个最优化问题，是关于求最大子集的，想请大家帮我想想。
> > 问题的具体情形是这样的：
>
> > 有一种指标dG，它能描述两两单链DNA互补杂交的热力学特征。我现在有400条DNA(编号为0，2，3...399)，它们组成一个集合；我现在要从这个集 合中找到一个子集，这个子集里的任意两两DNA的dG值大于等于一个值（m=1）。因为符合这样条件的子集很多，我要找到含有最多DNA个数的那个子集。
>
> > 我的方法是这样的：方便起见，400条DNA两两之间的dG，凡dG>=1的重新赋值为1，dG<1的重新赋值为0。我把这些值写入一个2维矩阵。如图1（见附 件）。含有最多1的那一行所代表的DNA被选出来，并且把所有与这个DNA杂交指标为1的其他DNA序列的相互关系写入一个新的2维矩阵，同时也会得到一个含有 最多1的那一行，把它选出来，重复上个运算。如此反复，最终筛选出来的DNA将组成最大子集。
> > 我用perl写出来这个算法，但是当我扩大总DNA数时出现了问题：理论上，最大子集中DNA个数将不小于扩大之前的，但是实际上，情况相反。
> > 请大家帮我看看，1）这个算法有问题吗？2）你能把你的办法写成伪代码告诉我吗？如果你能用perl写成源代码最好了。
>
> > --
> > Best regards,
> > Liu Jie
>
> > 020-32015312
> > Guangzhou Institutes of Biomedicine and Health, Chinese Academy of
> > Sciences
> >http://www.gibh.cas.cn/
>
> > --
> > 您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
> > 要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
> > 要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
> > 若有更多问题，请通过http://groups.google.com/group/perlchina?hl=zh-CN访问此网上论坛。
>
> > 感觉算法似乎有问题：
> > 举个反例吧，如果有九条DNA，分别编号0~8
> > 4
> > |
> > 1----0-----2 5------8
> > | | X |
> > 3 6-----7
>
> > 上图分别表示0和1,2,3,4的dg值>1；5 ,6 ,7 , 8之间两两dg >1，但是按照你的算法的话，
> > 首先取的DNA为0，但最大子集却是5,6,7,8（没有0）. 我也想不出什么好办法，等待高手吧。
>
> > --
> > 您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
> > 要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
> > 要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
> > 若有更多问题，请通过http://groups.google.com/group/perlchina?hl=zh-CN访问此网上论坛。
>
> --
> Best regards,
> Liu Jie
>
> 020-32015312
> Guangzhou Institutes of Biomedicine and Health, Chinese Academy of Scienceshttp://www.gibh.cas.cn/

--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。