Generating Non-Crosshybridizing Libraries

Question

[Jeol]

Recently, I am working on the solution for generating non-crosshybridizing libraries of DNA oligonucletides. UNAFOLD(http://mfold.rna.albany.edu/) helps me very much. I applied the "hybrid-ss-min.exe" to self-dimer analysis, finally I got 400 sequences from a ssDNA pool with 100,000 sequences. Nextly, I used the "hybrid-min.exe" to calculate minimum free energy between every ssDNA and every other, then save these datas into a 400×400 matrix for building a graph. In the graph, ssDNA is represented as vertex; And if the minimum free energy of hybridization is more than some threshold value(i.e. -1kcal/mol), an edge is placed between vertices, indicating there is non-crosshybridization. So, what I need to to is to find the maximal cliques. If I can do it, I will find the non-crosshybridizing library finally. Badly, there are not tools availble for large matrix, I found a perl moudle for 10×10 matrix(http://home.hiwaay.net/~gbacon/perl/clique.html) and a matlab tool for 50×50 matrix(http://www.mathworks.com/matlabcentral/fileexchange/19889-maximal-cliques). Could you please give me some advices?

Also, I find a paper about generating this kind of library, which gave a different strategy(http://www.springerlink.com/content/y4wy0mhcqdwy8c0t/). I plan to do it with this strategy. however, the files "hybrid-ss-min.exe" and "hybrid-min.exe" can not directly return the dG value, they write dG into a file. who there has the file with the same functions. THANKS in advance.

[Russh]

could you repost the springerlink. 400x400 doesn't seem a very big matrix to me, presumably it isn't sparse. How big a clique(s?) do you want to find?

[Jeol]

could you give me your address, I'll email it. it's as big as pissible, actually, I want to have about 100 sequences for tag DNA as luminex xTAG .

[Russh]

I'll give you pointers, but I ain't doing it. I mean, I wouldn't want to deny you the joy of solving your own problem ;0)

[Jeol]

I mean, I'll email the paper to you, there is a different way to generate the library. And we can discuss on it.

Answer 1

[Russh]

Try inverting the graph. Keep all the nodes as they are, and for any pair of nodes that are linked in your original graph there shouldn't be a link in the inversegraph (&viceversa).

Any nodes that are unconnected in the inversegraph are maximally connected in the original graph (I know that isn't quite what you want but its a good start) and id you extract those nodes from your originalgraph, they will form a maximal clique (cliquegraph).

Now you can either, alter your stringency until you get a decent number of unconnected nodes in your inversegraph (and hence a decent sized max clique), or at a given level of stringency, find nodes in your original graph that link to all members of cliquegraph and add them one at a time to cliquegraph (slow).

I think the clique finding methods start with dimercliques, from these find trimers, from these...

I'd have to have a play around to find out, but I'm fairly certain all this could be done in bioc/R - graph with RBGL.

Though, to my chagrin, R's graph library has been ejected from CRAN into Bioconductor (haven't used it in a year or so) so it might be on the way out. Perhaps igraph might be a better option?

EDIT: Forget most of the above. Put your data set into R's graph thing, boot up RBGL and run highlyConnSG() on it. Unlikely to give you a fully connected graph, but should be straightforward to trim the resulting graphs down using kCliques(). The latter might take a long time on your original graph, but should be ok once you've reduced its size

R

Answer 2

[Jeol]

russH, thanks for you suggestions. Finally, I find out it. the code written as follow:

m = matrix(scan("D:/xProject/Perl/matrix.txt", 400*400),400,400, + byrow=TRUE); g <- new("graphAM",adjMat=m, edgemode="directed"); h = ugraph(g); h = ugraph(g); maxClique(h)