在上面说的L中，有一个以上的全连通子图，目标是找出顶点最多的全连通子图。
Step 0， x 为L顶点列表，subG_list为空。
Step 1，x中任意找一个顶点。
Step 2，找出此顶点在L中所在的全连通子图，并把结果记录在subG_list中。
Step 3，x删除上一步结果中所有的全连通子图中的顶点。如果x空，结束。如果x非空，回到Step 0.
得到的subG_list应该是L的全连通子图集，再根据顶点个数排序就可以了。
400个点的图不算大，蛮力搜索应该不会用太久。不过一个图的全连通子图查找问题应该是一个比较经典的问题，肯定有经典算法的。我也没专门研究过图的算
法，不知道有没有工具能直接拿来用。
On 7月14日, 上午11时33分, Hydraphenix <hydrapheni...@gmail.com> wrote:
> 好像这个思路不行，有些DNA可能属于两个group，这个思路就没办法处理了。
> 看来这个问题难度超出我的想象啊。
>
> On 7月14日, 上午9时13分, Hydraphenix <hydrapheni...@gmail.com> wrote:
>
>
>
>
>
>
>
> > 最近也在用perl写矩阵相关的脚本。觉得你的问题，用矩阵就可以实现了。
> > 思路如下：
> > 做一个循环，给每个DNA分组，若这个dna的所有target中只有一个为1（自己），那么这个组就只有自己；若这个dna的target中有多个
> > 1，则检查target与group中的所有成员的score是否都为1，若是，加入group中，若不是，则不加入。
> > 这个循环做下来，每个DNA都有了分组，删除那些冗余的分组，剩下都是独立的分组，再统计每组成员的个数，就完成了。
>
> > On 7月12日, 下午8时19分, jie liu <liujie....@gmail.com> wrote:
>
> > > 大家好！
>
> > > 我这有个最优化问题，是关于求最大子集的，想请大家帮我想想。
> > > 问题的具体情形是这样的：
> > > 有一种指标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 Scienceshttp://www.gibh.cas.cn/
>
> > > matrix.txt
> > > 423K查看下载
>
> > > 图1.jpg
> > > 48K查看下载
--
您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。
要向此网上论坛发帖，请发送电子邮件至 perlchina@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 perlchina+unsubscribe@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
博文
