Dear JC, I tested your script on a huge data file output of Mash and it is working! Thanks a lot! Very nice script :)
Hi All, I intersected to data sets and I have a tabulated file with two columns like:
AA BB
BB CC
CC DD
BB AA
EE FF
FF GG
GG HH
II JJ
JJ II
II KK
... ...
and I would like to convert "one-to.one interactions" in clusters considering that AA interacts with BB, BB with CC and CC with DD (so AA, BB, CC and DD form a cluster). Similarly EE, FF, GG, HH form another cluster but none of these elements interact with elements of the first cluster and so on. I would like to obtain something like
AA BB CC DD
EE FF GG HH
II JJ KK
...
Would you please help me how I can do that?
3 answers
The data represents a graph in edge list format, i.e. each line is an edge of the graph specifying the two nodes that are connected. What you call clusters seems to be the connected components of this graph. So read the data into a graph structure then extract the connected components, e.g. in R with the igraph package, something like this (untested):
edge.list <- as.matrix(read.table("edge_list.txt",...)) # read the file as appropriate, turn data into a two-column matrix for use by igraph
G <- graph_from_edge_list(edge.list, directed = FALSE)
clusters <- components(G)
In pseudo code, if you want to try to write it
Initialize an 2D array : 2Darray
Import your file in a dataframe
Sort the dataframe by column one and column two, to get something like :
AA BB
BB AA
BB CC
CC DD
For each line of your dataframe
- If it's the first line of the datafame, create and
arrayand append first element and second element of the line - Else, does the first element exist in
array?- If yes, append
arraywith the second element - Else, append
2Darraywitharray, reinitilizearray, appendarraywith first element and second element
- If yes, append
At the end in 2Darray you will have your clusters.
Untested
You can use perl or python to get that:
#!/usr/bin/perl
use strict;
use warnings;
my %g = ();
my $a = undef;
my $b = undef;
my $net = 0;
my $fst = 1;
while (<>) {
chomp;
($a, $b) = split (/\s+/, $_);
if ($fst == 1) {
#warn "first iteration, adding $a - $b in net $net\n";
$g{$net}{$a} = 1;
$g{$net}{$b} = 1;
$fst = 0;
}
else {
my $new = 1;
for (my $n = 0; $n <= $net; $n++) {
if (defined $g{$n}{$a}) {
if (defined $g{$n}{$b}) {
#warn "$a - $b exist in net $n\n";
$new = 0;
last;
}
else {
#warn "$a exist in net $n, adding $b\n";
$g{$n}{$b} = 1;
$new = 0;
last;
}
}
else {
if (defined $g{$n}{$b}) {
#warn "$b exist in net $n, adding $a\n";
$g{$n}{$a} = 1;
$new = 0;
last;
}
}
}
if ($new == 1) {
$net++;
#warn "$a - $b not seen in other nets, adding in a new net $net\n";
$g{$net}{$a} = 1;
$g{$net}{$b} = 1;
}
}
}
#warn "writting nets\n";
foreach $net (sort keys %g) {
print join "\t", sort keys %{ $g{$net} };
print "\n";
}
Example:
$ perl graph.pl < data.txt
AA BB CC DD
EE FF GG HH
II JJ KK
Glad to help, how large was the data?
Log in to answer this question.
Question : If somewhere in the file you have BB GG, you want to get a single cluster (AA, BB, CC, DD, EE, FF, GG and HH) ?
I don't understand this line
Why is this tagged as a software error question ?