+ indep. WoS citations

Contents (hide)

  1. 1. Problem
  2. 2. "hf"
    1. 2.1 program
    2. 2.2 output
    3. 2.3 comments
  3. 3. "kd"
    1. 3.1 program
    2. 3.2 output
    3. 3.3 comments
  4. 4. "km"
    1. 4.1 program
    2. 4.2 output
    3. 4.3 comments
    4. 4.4 program / 2nd version
    5. 4.5 output
    6. 4.6 comments
  5. 5. "vk"
    1. 5.1 program
    2. 5.2 output
    3. 5.3 comments
  6. 6. "water"
    1. 6.1 program
    2. 6.2 output

1.  Problem

  • Read this abstract: http://pubmed.org/15372033
  • Go to this URL, click on enter and then click on data download. Go to the first table (Raw data), first line (transcription regulatory network data) and download the composite dataset. Click on readme for the description.
  • Count FFL and FBL subgraphs in this network.
    • FFL: A->B, A->C, B->C, not B->A, not C->A, not C->B
    • FBL (FeedBack Loop): A->B, B->C, C->A, other 3 links: no

2.  "hf"

2.1  program

#!/usr/bin/perl
use strict; use warnings;

my $infile="luscombe-trans-reg-net-all.txt";

open IN,$infile  or die "Couldn't open $infile: $! \n";;

my %dirNeiList;
while(<IN>){
    if(/([^\#\s]\S*)\s+(\S+)/){

	    ++${$dirNeiList{$1}}{$2};

    }
}
close IN;

my $ffl;
#count FFL: A->B, A->C, B->C, not B->A, not C->A, not C->B
for my $nodeA (grep{1<scalar keys %{$dirNeiList{$_}}}keys %dirNeiList){# slect A
    for my $nodeB(grep{scalar keys %{$dirNeiList{$_}}}keys %{$dirNeiList{$nodeA}}){ #select A ->B
	for my $nodeC(grep{defined ${$dirNeiList{$nodeA}}{$_}}keys %{$dirNeiList{$nodeB}}){ #select B->C->A

	    if (      !defined ${$dirNeiList{$nodeB}}{$nodeA}    #  no B->A 
		   && !defined ${$dirNeiList{$nodeC}}{$nodeA}    # no C->A 
		   && !defined ${$dirNeiList{$nodeC}}{$nodeB}     # no C->B 
		   ) {
	    $ffl++;
	    }
	}
    }
}
print "The number of FFL loops is: ".$ffl."\n";  
#count FBL (FeedBack Loop): A->B, B->C, C->A,
my $fbl;
for my $nodeA ( grep{0 < scalar keys %{$dirNeiList{$_}}} keys %dirNeiList ){
   for my $nodeB ( grep{scalar keys %{ $dirNeiList {$_}} && !defined ${$dirNeiList {$_}}{$nodeA}} keys %{$dirNeiList {$nodeA}} ) { # A->B no B-A link!
      for my $nodeC ( grep { !defined ${$dirNeiList{ $_ }}{ $nodeB } } keys %{$dirNeiList { $nodeB }} ){ # B - >C no C-B link
        if ( defined ${$dirNeiList{ $nodeC }}{ $nodeA } && !defined ${$dirNeiList{ $nodeA }}{ $nodeC } # C->A , no A-C 
	     &&(($nodeA lt $nodeB && $nodeB lt $nodeC) || ($nodeA lt $nodeC && $nodeC lt $nodeB) )) #  don't count rotation
                        { ++$fbl; }
      }
   }
 }
print "The number of FBL loops is: ".$fbl."\n";

2.2  output

The number of FFL loops is: 858
The number of FBL loops is: 3

2.3  comments

  • OK
  • The acronyms "FFL" and "FBL" already contain "loop" (the letter L). It's not necessary to add "loop" to "FBL" or "FFL".

3.  "kd"

3.1  program


#! /usr/bin/perl -w
use strict;

my %network;

# building the interaction network
&buildNetworkFromFile("luscombe-trans-reg-net-all.txt", \%network);

# looking for FFLs
print "FFL ::: ".&countFFLs(\%network)."\n";

# looking for FBLs
print "FBL ::: ".&countFBLs(\%network)."\n";


#################################################x

sub buildNetworkFromFile {
	my ($filename, $network) = @_;

	open (IN, "<".$filename) or die $!;
	while (<IN>) {
		if (!/^\s*(#|$)/) {
			/(\w*)\s*(\w*)/;
			++${$network{$1}}{$2};
		}
	}
	close IN;
}

sub countFFLs {
	my $network = shift;
	my $nFFL;

	for my $A (grep{1<scalar keys %{$network{$_}} } keys %network) {
		for my $B (grep {scalar keys %{$network{$_}} && !defined ${$network{$_}}{$A} } keys %{$network{$A}} ) {
			for my $C (grep{ !defined ${$network{$_}}{$B} && !defined ${$network{$_}}{$A} && defined ${$network{$A}}{$_} } keys %{$network{$B}}) {
				$nFFL++;
			}	
		}
	}
	return $nFFL;
}

sub countFBLs {
	my $network = shift;
	my $nFBL;

	for my $A (grep{scalar keys %{$network{$_}} } keys %network) {
		for my $B (grep {scalar keys %{$network{$_}} && !defined ${$network{$_}}{$A} } keys %{$network{$A}} ) {
			for my $C (grep{scalar keys %{$network{$_}} && !defined ${$network{$_}}{$B} && defined ${$network{$_}}{$A} && !defined ${$network{$A}}{$_} } keys %{$network{$B}}) {
				$nFBL++;
			}	
		}
	}
	return $nFBL/3;
}

3.2  output

FFL ::: 858
FBL ::: 3

3.3  comments

  • OK
  • Would it be possible to count FFLs and FBLs in the same routine?

4.  "km"

4.1  program


#!/usr/bin/perl
use strict; use warnings;
open IN, "luscombe-trans-reg-net-all.txt";

# We look for feed-forward loops and feedback loops in the transciptional network of the yeast.
# Definition of a feed-forward loop: if x => [x1][x2], y => [y1][y2], z => [z1][z2], then (x1 = z1) & (x2 = y1) & (y2 = z2) (x =/= y =/= z).
# Definition of a feed-forward loop: if x => [x1][x2], y => [y1][y2], z => [z1][z2], then (x1 = z2) & (x2 = y1) & (y2 = z1) (x =/= y =/= z).

my %interactions;

while (<IN>) {
if (/([^\#\s]\S*)\s+(\S+)/)
{ ++$ { $interactions{ $1 } } { $2 } };
}
close IN;

#looking for FFLs

my $ffl;

for my $nodeA ( grep { 1 < scalar keys %{$interactions{ $_ } } } keys %interactions ) { # take those nodes which have more than one outgoing links
    for my $nodeB ( grep { scalar keys % { $interactions { $_ }} && !defined ${$interactions { $_ }}{ $nodeA } } keys %{$interactions { $nodeA }} ) { # no B-A link!
            for my $nodeC ( grep { !defined ${$interactions{ $_ }}{ $nodeB } } keys %{$interactions { $nodeB }} ){ # no C-B link
                if ( (defined ${$interactions{ $nodeA }}{ $nodeC } && !defined ${$interactions{ $nodeC }}{ $nodeA }) )# A-C link exists, C-A link does not
                        { ++$ffl; }
                    }
                }
            }

print "The number of feed-forward loops is: ".$ffl."\n";

#looking for FBLs

my $fbl;

for my $nodeA ( grep { 0 < scalar keys %{$interactions{ $_ } } } keys %interactions ) {
   for my $nodeB ( grep { scalar keys %{ $interactions { $_ }} && !defined ${$interactions { $_ }}{ $nodeA } } keys %{$interactions { $nodeA }} ) { # no B-A link!
      for my $nodeC ( grep { !defined ${$interactions{ $_ }}{ $nodeB } } keys %{$interactions { $nodeB }} ){ # no C-B link
        if ( defined ${$interactions{ $nodeC }}{ $nodeA } && !defined ${$interactions{ $nodeA }}{ $nodeC } ) # C-A link exists, A-C link does not
                        { ++$fbl; }
                    }
                }
            }

print "The number of feedback loops is: ".$fbl."\n";

4.2  output

The number of feed-forward loops is: 858
The number of feedback loops is: 9

4.3  comments

  • OK
  • nice: grep and defined
  • don't you need to divide the number of FBLs by 3?
  • try to make the code more readable with indentations, example:
for my $nodeA (grep{    ...
                     && ... } keys %something)
{
    other for loop
    {
         third for loop
         {
             ...
         }
    }
}

4.4  program / 2nd version

#!/usr/bin/perl
use strict; use warnings;
open IN, "luscombe-trans-reg-net-all.txt";

# We look for feed-forward loops and feedback loops in the transciptional network of the yeast.
# Definition of a feed-forward loop: if x => [x1][x2], y => [y1][y2], z => [z1][z2], then (x1 = z1) & (x2 = y1) & (y2 = z2) (x =/= y =/= z).
# Definition of a feed-forward loop: if x => [x1][x2], y => [y1][y2], z => [z1][z2], then (x1 = z2) & (x2 = y1) & (y2 = z1) (x =/= y =/= z).

my %interactions;

while (<IN>) {
if (/([^\#\s]\S*)\s+(\S+)/)
{ ++$ { $interactions{$1} } { $2 } };
}
close IN;

#looking for FFLs

my $ffl;

for my $nodeA ( grep { 1 < scalar keys %{$interactions{ $_ } } } keys %interactions ) { # take those nodes which have more than one outgoing links
    for my $nodeB ( grep { scalar keys % { $interactions { $_ }} && !defined ${$interactions { $_ }}{ $nodeA } } keys %{$interactions { $nodeA }} ) { # no B-A link!
            for my $nodeC ( grep { !defined ${$interactions{ $_ }}{ $nodeB } } keys %{$interactions { $nodeB }} ){ # no C-B link
                if ( (defined ${$interactions{ $nodeA }}{ $nodeC } && !defined ${$interactions{ $nodeC }}{ $nodeA }) )# A-C link exists, C-A link does not
                        { ++$ffl; }
                    }
                }
            }

print "The number of feed-forward loops is: ".$ffl."\n";

#looking for FBLs

my $fbl;

for my $nodeA ( grep { 0 < scalar keys %{$interactions{ $_ } } } keys %interactions ) {
   for my $nodeB ( grep { scalar keys %{ $interactions { $_ }} && !defined ${$interactions { $_ }}{ $nodeA } } keys %{$interactions { $nodeA }} ) { # no B-A link!
      for my $nodeC ( grep { !defined ${$interactions{ $_ }}{ $nodeB } } keys %{$interactions { $nodeB }} ){ # no C-B link
        if ( defined ${$interactions{ $nodeC }}{ $nodeA } && !defined ${$interactions{ $nodeA }}{ $nodeC } ) # C-A link exists, A-C link does not
                        { ++$fbl; }
                    }
                }
            }

# as FB loops are circular (A->B->C->A...), the algorithm above counts one FBL as 3. Therefore this number should be divided by 3.

my $realfbl = $fbl/3;

print "The number of feedback loops is: ".$realfbl."\n";

4.5  output

The number of feed-forward loops is: 858
The number of feedback loops is: 3

4.6  comments

  • OK

5.  "vk"

5.1  program


#!/usr/bin/perl

# this program reads a directed network from "input.txt" and counts
# the number os FFLs (feedforward loop) and FBLs (feedback loop) in
# the network. output printed to the standard output

use strict; use warnings;

# subroutine read_directed_network
# parameters: 1. name of the input file
#             2. reference to a hash variable
# function: - open input file. If it cannot be opened,
#                subroutine raises an exception
#           - read lines of the file
#           - fill the hash variable (network) with references
#                of hashes (nested hashes), where the keys of the network (key1)
#                are the values of the first column in the file, and
#                the keys of the values of the network (key2) are the values
#                of the second column in the file (belong to their key1).
#                values of the nested hashes are the number of the links
#                from key1 to key2 (usually 1).
#           -close input file and return
sub read_directed_network{
    my ($infile, $nei_ref) = @_;
    open IN, $infile or die "Couldn't open $infile: $! \n"; # open input file
    while (<IN>) {
	if (!/^\s*(\#|$ )/x) {  # ignore comment and empty lines
	    if (/(\S+)\s+(\S+)/) {
		++${ $$nei_ref{ $1 } }{ $2 }; # insert field1 and field2 into the hash
                                        # in a directed network-like, nested-hash
                                        # structure, or increment the link-counter
	    }
	}
    }
    close IN;

} # end of read_directed_network

#----------------------------------------------------------------

# subroutine count_ffl
# parameters: 1. reference to a hash variable (containing a directed network)
# return value: integer, the number of FFLs in the network
# function: - iterate over the nodes of the network and count the
#                occurrences of FFL (feedforward loop) configurations
#                like: A->B, B->C, A->C, and no other links between A, B and C
#           - return the result
sub count_ffl{
    my $nei_ref = $_[0];
    my $ffls = 0;

    for my $nodeA (grep{1<scalar keys%{$$nei_ref{ $_ }}} keys%{ $nei_ref }) { # 1 < kout(A)
	for my $nodeB (grep {scalar keys%{ $$nei_ref{ $_ } } } keys%{ $$nei_ref{ $nodeA } }){ # 0 < kout(B)
	    for my $nodeC (grep{defined ${ $$nei_ref{ $nodeA } }{ $_ } } keys% { $$nei_ref{ $nodeB } }){ # A->C exists
		if (   !defined ${ $$nei_ref{ $nodeB }}{ $nodeA }     # if there is no B->A link
		    && !defined ${ $$nei_ref{ $nodeC }}{ $nodeA }     # if there is no C->A link
		    && !defined ${ $$nei_ref{ $nodeC }}{ $nodeB }) {  # if there is no C->B link
			++$ffls;
		}
	    }
	}
    }
    return $ffls;
} # end of count_ffl

#------------------------------------------------------------------

# subroutine count_fbl
# parameters: 1. reference to a hash variable (containing a directed network)
# return value: integer, the number of FBLs in the network
# function: - iterate over the nodes of the network and count the
#                occurrences of FBL (feedback loop) configurations
#                like: A->B, B->C, C->A, and no other links between A, B and C
#           - return the result
sub count_fbl{
    my $nei_ref = $_[0];
    my $fbls = 0;

    for my $nodeA (grep{scalar keys%{ $$nei_ref{ $_ } }} keys%{ $nei_ref }) { # 0 < kout(A)
	for my $nodeB (grep {scalar keys%{$$nei_ref{$_ }}} keys%{$$nei_ref{$nodeA }}){ # 0 < kout(B)
	    for my $nodeC (grep{defined ${$$nei_ref{$_}}{$nodeA }} keys%{$$nei_ref{$nodeB }}){ # C->A exists
		if (   !defined ${$$nei_ref{$nodeB }}{$nodeA }    # there is no B->A link
		    && !defined ${$$nei_ref{$nodeA }}{$nodeC }    # there is no A->C link
		    && !defined ${$$nei_ref{$nodeC }}{$nodeB }) { # there is no C->B link
			++$fbls;
		}
	    }
	}
    }
    return $fbls;
} # end of count_fbl

#============================= MAIN ================================

my %dirNeiList;

&read_directed_network("input.txt",\%dirNeiList);
my $ffl_number = &count_ffl(\%dirNeiList);
my $fbl_number = &count_fbl(\%dirNeiList);

print "Number of FFLs in the network: $ffl_number\n";
print "Number of FBLs in the network: $fbl_number\n";

5.2  output


Number of FFLs in the network: 858
Number of FBLs in the network: 9

5.3  comments

  • Nice work, almost OK.
  • Shouldn't the number of FBLs be divided by 3?
  • Is it possible to count FFLs and FBLs with a single subroutine? The only difference between the two subgraphs is that the FFL contains an A-->C link, but no C-->A link, while the FBL contains a C-->A link, but no A-->C link.

6.  "water"

6.1  program


#!/usr/bin/perl
use strict; use warnings; use Switch;

# ============ parameters ===================

my $URL = "http://sandy.topnet.gersteinlab.org/data/luscombe-trans-reg-net-all.txt";

# ============== function definitions =================

sub read_dirNeiList_fromUrl
{
    my ($url,$dirNeiList) = @_;

    # clear output data
    %$dirNeiList = ();

    # open input, read data (not comment) lines, save directed links, close input
    open IN, "wget \"$url\" -O - |"; while(<IN>){ if(/([^\#\s]\S*)\s+(\S+)/){ ++${$$dirNeiList{$1}}{$2} }} close IN;
}

# ----------------------------------------------

sub print_subgraphNum
{
    my ($dirNeiList,$subgraphType) = @_;

    # number of subraphs of the selected type
    my $n;

    # abbreviation (shorthand) for 'dirNeiList'
    my $d = $dirNeiList;

    # handle each subgraph type
    switch ($subgraphType) {
        # FFL and FBL handled together
        # FFL: A->B, A->C, B->C, not B->A, not C->A, not C->B
        # FBL (FeedBack Loop): A->B, B->C, C->A, other 3 links: no
        case [qw<FFL FBL>] {
            #
            # loop through the list of nodes with at least one outgoing link
            for my $nodeA (keys %$d){
                # loop through the list of nodeB neighbors with at least one outgoing,
                # but no back link (B->A)
                for my $nodeB (grep{ scalar keys %{$$d{ $_ }} && !defined ${$$d{ $_ }}{ $nodeA } } keys %{$$d{ $nodeA }}){
                    # loop through the list of nodeC neighbors with no back link (C->B)
                    for my $nodeC (grep{ !defined ${$$d{ $_ }}{ $nodeB } } keys %{$$d{ $nodeB }}){
                        # FFL: A->C yes, C->A no
                        # FBL: C->A yes, A->C no
                        # NOTE: for FBL the 3 nodes can be rotated (cyclic permutation)
                        #       count each FBL only once by requiring (A lt B lt C) OR (A lt C lt B)
                        if(   (   "FFL" eq $subgraphType
                               && defined${$$d{ $nodeA }}{ $nodeC } && !defined${$$d{ $nodeC }}{ $nodeA }
                              )
                           || (   "FBL" eq $subgraphType
                               && defined${$$d{ $nodeC }}{ $nodeA } && !defined${$$d{ $nodeA }}{ $nodeC }
                               && (   ($nodeA lt $nodeB && $nodeB lt $nodeC)
                                   || ($nodeA lt $nodeC && $nodeC lt $nodeB) )
                              )
                          )
                        {
                            # if("FBL" eq $subgraphType){ print $nodeA.", ".$nodeB.", ".$nodeC."\n"; } # test
                            ++$n;
                        }
                    }
                }
            }
        }
        else {
            die "Error, subgraph type not (yet) available: ".$subgraphType."\n";
        }
    }

    # print result
    print "Number of ".$subgraphType." subgraphs: ".$n."\n";
}

# ============= main =================

# read the list of directed links from a URL
my %dirNeiList; &read_dirNeiList_fromUrl( $URL, \%dirNeiList );

# print the number of subgraphs of each selected type
for (qw<FFL FBL>){ &print_subgraphNum( \%dirNeiList, $_ ) }

6.2  output

Number of FFL subgraphs: 858
Number of FBL subgraphs: 3