谢谢各位哈，总算找到办法了，虽然最终发现是个NPC问题。
另外，请问各位有谁做RNA结构预测相关的事情？ 2011/7/15 朱岩 <[email protected]> > 不好意思，index搞错了，下面是修改版，用的Jie Liu的矩阵， > 得到结果(index从0开始)： > 0 1 3 > 0 1 4 > 0 2 4 > 2 4 7 > 4 7 9 > 好像vertex number不能取10以上(包括10)...看看能不能根据作者的算法重写吧 > > > use strict; > use Graph::Clique; > > > > my @edges; > my %h; > my $nnz; # num of non-zeros > > > # build up undirected graph > open F, 'matrix_small.txt' or die; > while(<F>){ > my $i = $.-1; > my @a = split(/ /,$_); > for my $j (0..$#a){ > if ($a[$j] == 1){ > $nnz++; > my $e = $i <= $j ? $i.",".$j : $j.",".$i; > $h{$e}++; > } > } > } > close F; > > > foreach my $key (sort keys %h){ > my @a = split(/\,/, $key); > push @edges, [@a]; > } > > > > # find maximal clique > > my @cliques; > > for (my $k=int(sqrt($nnz)); $k>0; $k--){ > @cliques = getcliques($k,\@edges); > if ($#cliques >=0){ last; } > } > > print join("\n", @cliques),"\n"; > > > > 在 2011年7月14日 下午11:16，nixin <[email protected]>写道： > > google到的matlab的maximal cliques程序： >> http://www.mathworks.com/matlabcentral/fileexchange/19889-maximal-cliques >> >> >> On Jul 14, 9:27 pm, jie liu <[email protected]> wrote: >> > 附件忘加了，在这个邮件里 >> > >> > 2011/7/14 jie liu <[email protected]> >> > >> > >> > >> > >> > >> > >> > >> > >> > >> > >> > >> > > 朱岩，出了一些状况. 我造了一个 无向图 的矩阵数据。 >> > > ------------data---------------- >> > > 0 0 0 0 0 0 0 0 0 0 >> > > 1 0 0 0 0 0 0 0 0 0 >> > > 1 0 0 0 0 0 0 0 0 0 >> > > 1 1 0 0 0 0 0 0 0 0 >> > > 1 1 1 0 0 0 0 0 0 0 >> > > 0 0 0 0 0 0 0 0 0 0 >> > > 0 0 0 0 0 0 0 0 0 0 >> > > 0 0 1 0 1 0 0 0 0 0 >> > > 0 0 0 0 0 0 0 0 0 0 >> > > 0 0 0 0 1 0 0 1 0 0 >> > > -------------------- >> > > 我用matlab可视化了这个graph，请见附件。 >> > >> > > >> 之后我用你的程序（我把K值改成了K>1）处理这个矩阵，显示的结果是：2，6，9这个节点。这与附件的图矛盾啊，2，6，9实际不是完全连通图啊。怎么回事？ >> 我先把结果反馈给大家，同时我也想想 >> > >> > > ------------ perl script-------------------- >> > >> > > use strict; >> > > use Graph::Clique; >> > >> > > my @edges; >> > > my %h; >> > > my $nnz; # num of non-zeros >> > >> > > # build up undirected graph >> > > open FASTA, "<@ARGV"; >> > > while (<FASTA>) { >> > > my $i = $. + 1; >> > > my @a = split( / /, $_ ); >> > > for my $j ( 0 .. $#a ) { >> > > if ( $a[$j] ) { >> > > $nnz++; >> > > my $e = $i <= $j ? $i . "," . $j : $j . "," . $i; >> > > $h{$e}++; >> > > } >> > > } >> > > } >> > >> > > foreach my $key ( sort keys %h ) { >> > > my @a = split( /\,/, $key ); >> > > push @edges, [@a]; >> > > } >> > >> > > # find maximal clique >> > >> > > my @cliques; >> > >> > > for ( my $k = int( sqrt($nnz) ) ; $k > 1 ; $k-- ) { >> > > @cliques = getcliques( $k, \@edges ); >> > > if ( $#cliques >= 0 ) { >> > > last; >> > > } >> > > } >> > >> > > print join( "\n", @cliques ), "\n"; >> > >> > > ------------end-------------------------------- >> > > 2011/7/14 朱岩 <[email protected]> >> > >> > >> 读文件把while(<DATA>)换成while(<F>)就可以了 >> > >> > >> 在 2011年7月14日 下午4:02，jie liu <[email protected]>写道： >> > >> > >>> 我刚刚也看到了，还去了作者给的一个地址（http://home.hiwaay.net/~gbacon/perl/clique.html >> > >>> ）看来一下，很激动！就是我要找的，谢谢大家了哈。 >> > >> > >>> >> 但是，我都perl不熟，现在我把矩阵存在txt里了（1代表有边，0代表无边），我怎么把矩阵读进去，然后形成graph，然后用clique呢...朱岩的 >> 程序我使了下，没成功。朱岩的程序里我没有看到读入的操作啊（实在是对perl不熟悉...） >> > >> > >>> 2011/7/14 nixin <[email protected]> >> > >> > >>>> 果然有现成的库。clique这个关键词没有掌握，搜了好一会全连通图，啥也没搜到。呵呵。 >> > >> > >>>> On 7月14日, 下午1时28分, 朱岩 <[email protected]> wrote: >> > >>>> > 图论解法： >> > >> > >>>> > 找最大完全连通子图，可以用Graph::Clique，当然应该还有更好的算法； >> > >>>> > 这里只举了个10x10的小例子 >> > >>>> > 用非零数的平方根作为最大子图顶点数的上限 >> > >> > >>>> > use strict; >> > >>>> > use Graph::Clique; >> > >> > >>>> > my @edges; >> > >>>> > my %h; >> > >>>> > my $nnz; # num of non-zeros >> > >> > >>>> > # build up undirected graph >> > >> > >>>> > while(<DATA>){ >> > >>>> > my $i = $.+1; >> > >>>> > my @a = split(/ /,$_); >> > >>>> > for my $j (0..$#a){ >> > >>>> > if ($a[$j]){ >> > >>>> > $nnz++; >> > >>>> > my $e = $i <= $j ? $i.",".$j : $j.",".$i; >> > >>>> > $h{$e}++; >> > >>>> > } >> > >>>> > } >> > >> > >>>> > } >> > >> > >>>> > foreach my $key (sort keys %h){ >> > >>>> > my @a = split(/\,/, $key); >> > >>>> > push @edges, [@a]; >> > >> > >>>> > } >> > >> > >>>> > # find maximal clique >> > >> > >>>> > my @cliques; >> > >> > >>>> > for (my $k=int(sqrt($nnz)); $k>3; $k--){ >> > >>>> > @cliques = getcliques($k,\@edges); >> > >>>> > if ($#cliques >=0){ >> > >>>> > last; >> > >>>> > } >> > >> > >>>> > } >> > >> > >>>> > print join("\n", @cliques),"\n"; >> > >> > >>>> > __DATA__ >> > >>>> > 0 0 1 0 1 0 0 0 0 0 >> > >>>> > 0 1 1 0 0 0 0 0 0 0 >> > >>>> > 1 1 1 0 1 0 0 1 0 0 >> > >>>> > 1 1 1 0 0 0 0 0 0 0 >> > >>>> > 1 1 1 0 1 0 0 1 0 1 >> > >>>> > 0 0 0 0 0 0 0 0 0 0 >> > >>>> > 0 0 0 0 0 0 0 0 0 0 >> > >>>> > 0 0 1 0 1 0 0 1 0 1 >> > >>>> > 0 0 0 0 0 0 0 0 0 0 >> > >>>> > 0 0 0 0 1 0 0 1 0 0 >> > >> > >>>> -- >> > >>>> 您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。 >> > >>>> 要向此网上论坛发帖，请发送电子邮件至 [email protected]。 >> > >>>> 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。 >> > >>>> 若有更多问题，请通过http://groups.google.com/group/perlchina?hl=zh-CN >> 访问此网上论坛。 >> > >> > >>> -- >> > >>> Best regards, >> > >>> Liu Jie >> > >> > >>> 020-32015312 >> > >>> Guangzhou Institutes of Biomedicine and Health, Chinese Academy of >> > >>> Sciences >> > >>>http://www.gibh.cas.cn/ >> > >> > >>> -- >> > >>> 您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。 >> > >>> 要向此网上论坛发帖，请发送电子邮件至 [email protected]。 >> > >>> 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。 >> > >>> 若有更多问题，请通过http://groups.google.com/group/perlchina?hl=zh-CN访问此网上论坛。 >> > >> > >> -- >> > >> Yours, Yan Zhu >> > >> > >> Institute of Microbiology, Chinese Academy of Sciences >> > >> > >> Datun Rd. >> > >> Chaoyang District >> > >> Beijing 100101 >> > >> P. R. China >> > >> > >> -- >> > >> 您收到此邮件是因为您订阅了 Google 网上论坛的"PerlChina Mongers 讨论组"论坛。 >> > >> 要向此网上论坛发帖，请发送电子邮件至 [email protected]。 >> > >> 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。 >> > >> 若有更多问题，请通过http://groups.google.com/group/perlchina?hl=zh-CN访问此网上论坛。 >> > >> > > -- >> > > Best regards, >> > > Liu Jie >> > >> > > 020-32015312 >> > > Guangzhou Institutes of Biomedicine and Health, Chinese Academy of >> > > Sciences >> > >http://www.gibh.cas.cn/ >> > >> > -- >> > Best regards, >> > Liu Jie >> > >> > 020-32015312 >> > Guangzhou Institutes of Biomedicine and Health, Chinese Academy of >> Scienceshttp://www.gibh.cas.cn/ >> > >> > Graph.jpg >> > 30KViewDownload >> >> -- >> 您收到此邮件是因为您订阅了 Google 网上论坛的“PerlChina Mongers 讨论组”论坛。 >> 要向此网上论坛发帖，请发送电子邮件至 [email protected]。 >> 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。 >> 若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。 >> >> > > > -- > Yours, Yan Zhu > > Institute of Microbiology, Chinese Academy of Sciences > > Datun Rd. > Chaoyang District > Beijing 100101 > P. R. China > > -- > 您收到此邮件是因为您订阅了 Google 网上论坛的“PerlChina Mongers 讨论组”论坛。 > 要向此网上论坛发帖，请发送电子邮件至 [email protected]。 > 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。 > 若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。 > -- Best regards, Liu Jie 020-32015312 Guangzhou Institutes of Biomedicine and Health, Chinese Academy of Sciences http://www.gibh.cas.cn/ -- 您收到此邮件是因为您订阅了 Google 网上论坛的“PerlChina Mongers 讨论组”论坛。 要向此网上论坛发帖，请发送电子邮件至 [email protected]。 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。 若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
