[Bio] / FigKernelScripts / find_subsys.pl Repository:
ViewVC logotype

View of /FigKernelScripts/find_subsys.pl

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.3 - (download) (as text) (annotate)
Wed Jan 30 19:29:31 2008 UTC (11 years, 9 months ago) by overbeek
Branch: MAIN
CVS Tags: mgrast_dev_08112011, rast_rel_2009_05_18, mgrast_dev_08022011, rast_rel_2014_0912, rast_rel_2008_06_18, myrast_rel40, rast_rel_2008_06_16, mgrast_dev_05262011, rast_rel_2008_12_18, mgrast_dev_04082011, rast_rel_2008_07_21, rast_rel_2010_0928, rast_2008_0924, mgrast_version_3_2, mgrast_dev_12152011, rast_rel_2008_04_23, mgrast_dev_06072011, rast_rel_2008_09_30, rast_rel_2009_0925, rast_rel_2010_0526, rast_rel_2014_0729, mgrast_dev_02212011, rast_rel_2010_1206, mgrast_release_3_0, mgrast_dev_03252011, rast_rel_2010_0118, mgrast_rel_2008_0924, mgrast_rel_2008_1110_v2, rast_rel_2009_02_05, rast_rel_2011_0119, mgrast_rel_2008_0625, mgrast_release_3_0_4, mgrast_release_3_0_2, mgrast_release_3_0_3, mgrast_release_3_0_1, mgrast_dev_03312011, mgrast_release_3_1_2, mgrast_release_3_1_1, mgrast_release_3_1_0, mgrast_dev_04132011, rast_rel_2008_10_09, mgrast_dev_04012011, rast_release_2008_09_29, mgrast_rel_2008_0806, mgrast_rel_2008_0923, mgrast_rel_2008_0919, rast_rel_2009_07_09, rast_rel_2010_0827, mgrast_rel_2008_1110, myrast_33, rast_rel_2011_0928, rast_rel_2008_09_29, mgrast_rel_2008_0917, rast_rel_2008_10_29, mgrast_dev_04052011, mgrast_dev_02222011, rast_rel_2009_03_26, mgrast_dev_10262011, rast_rel_2008_11_24, rast_rel_2008_08_07, HEAD
Changes since 1.2: +1 -1 lines
allow loose matching in rapid_propagation


#################################################################################
#
# Usage: find_subsys SubsystemName Roles Definitions BooleanExpressions GenomeDir > Output
# 
# INPUT
# -----
# 
# SubsystemName: just the character string name of the subsystem
# 
# Roles is a file in which each line contains 
#
#       Abbrev \t FunctionalRole
#
# Definitions is a file containing lines of the form
#
#       Abbrev \t BoolExp
#
# BooleanExpressions: a file of lines of the form
# 
# 	Variant-Code \t BoolExp
# 
#     where Variant-Code is a string [-1 and 0 have the normal special meanings]
#  
#           BoolExp is one of the following
# 
# 		Abbrev
# 		not BoolExp1
# 		BoolExp1 or BoolExp2
# 	        BoolExp1 and BoolExp2
# 		BoolExp1 -> BoolExp2
# 		(BoolExp1)
#               \d+ of {BoolExp1,BoolExp2,...BoolExpN}
# 
# LibraryOfFigFams is a standard FigfamsData directory that contains at least
# families corresponding to each of the FigFamIDs occurring in the
# BooleanExpressions
# 
# 
# OUTPUT
# ------
# 
# SubsystemName
# Variant-Code [corresponding to the first "true" rule]
# FigFamID \t PEG \t LOC \t Function
# FigFamID \t PEG \t LOC \t Function
# FigFamID \t PEG \t LOC \t Function
# 	.
# 	.
# 	.
# 	.
# 	.
# //
# 
# The last line is included so that one could run a sequence of searches simply
# appending the output to a single file.
# 
#################################################################################

use strict;
use FIG;
my $fig = new FIG;

my $usage = "usage: find_subsystem SubsystemName Roles Definitions BooleanExpressions GenomeDir > Output";

my($subsys_name,$rolesF,$booleanF,$defF,$figfamsD,$genomeD);
(
 ($subsys_name = shift @ARGV) &&
 ($rolesF      = shift @ARGV) &&
 ($defF        = shift @ARGV) &&
 ($booleanF    = shift @ARGV) &&
 ($genomeD     = shift @ARGV)
)
    || die $usage;

print "$subsys_name\n";

my $abbrev_to_loc = {};
my $encoding = [[],0];   # Encoding is a 2-tuple [Memory,NxtAvail]

my @roles = &load_roles($encoding,$abbrev_to_loc,$rolesF);
&load_definitions($encoding,$abbrev_to_loc,$defF);

my @rules = &parse_rules($encoding,$abbrev_to_loc,$booleanF);

# foreach my $tuple (@rules)
# {
#     my($vc,$bool) = @$tuple;
#     print "$vc\n";
#     &print_bool($bool);
#     print "\n\n";
# }

use ToCall;
my $genomeO = new ToCall($genomeD);

use FigFams;
my $figfams = new FigFams($fig,$figfamsD);

my $rule;
my $role_to_pegs = {};

my $role;
my $relevant_genes = {};
foreach $role (@roles)
{
    $relevant_genes->{$role} = &gather_genes($fig,$genomeO,$figfams,$role);
}
# print STDERR &Dumper($relevant_genes);

my($i,$matched);
for ($i=0, $matched=undef; (! defined($matched)) && ($i < @rules); $i++)
{
#   print &Dumper($rules[$i],$matched);
    $matched = &is_rule_true($rules[$i],$relevant_genes);
}

my $variant_code = defined($matched) ? $matched : -1;
print "$variant_code\n";

my %seen;           # to avoid displaying the same multifunctional peg more than once
foreach $role (sort keys(%$relevant_genes))
{
    my $hits = $relevant_genes->{$role};
    my $hit;
    foreach $hit (@$hits)
    {
	my($peg,$loc,$function) = @$hit;
	if (! $seen{$peg})
	{
	    print join("\t",($role,$peg,$loc,$function)),"\n";
	    $seen{$peg} = 1;
	}
    }
}
print "//\n";

sub parse_rules {
    my($encoding,$abbrev_to_loc,$booleanF) = @_;

    my @rules = ();
    foreach $_ (`cat $booleanF`)
    {
	my($boolexp,$variant_code,$loc);
	if (($_ =~ /^\s*(\S+)\s+(\S.*\S)\s*$/) &&
	    (($variant_code,$boolexp) = ($1,$2)) &&
	    defined($loc = &parse_bool($boolexp,$encoding,$abbrev_to_loc)))
	{
	    push(@rules,[$variant_code,[$encoding->[0],$loc]]);
	}
    }
    return @rules;
}

sub parse_bool {
    my($s,$encoding,$abbrev_to_loc) = @_;

    my $input = $s;
    my $abbrev;
    foreach $abbrev (sort { length($b) <=> length($a) } keys(%$abbrev_to_loc))
    {
	my $loc = $abbrev_to_loc->{$abbrev};
	my $abbrevQ = quotemeta $abbrev;
	while ($s =~ s/(^|[\s\{,(])($abbrevQ)($|[\s\},)])/$1<$loc>$3/) {}
    }
    my $got = 0;
    while ($s !~ /^\s*<\d+>\s*$/)
    {
	my $nxt = $encoding->[1];
	if ($s =~ s/\(\s*(<\d+>)\s*\)/$1/)
	{
	    $got = 1;
	}
	elsif ($s =~ s/not\s+<(\d+)>/<$nxt>/)
	{
	    &add_to_encoding($encoding,["not",$1]);
	    $got = 1;
	}
	elsif ($s =~ s/<(\d+)>\s+and\s+<(\d+)>/<$nxt>/)
	{
	    &add_to_encoding($encoding,["and",$1,$2]);
	    $got = 1;
	}
	elsif ($s =~ s/<(\d+)>\s+or\s+<(\d+)>/<$nxt>/)
	{
	    &add_to_encoding($encoding,["or",$1,$2]);
	    $got = 1;
	}
	elsif ($s =~ s/<(\d+)>\s+->\s+<(\d+)>/<$nxt>/)
	{
	    &add_to_encoding($encoding,["->",$1,$2]);
	    $got = 1;
	}

	elsif ($s =~ s/(\d+)\s+of\s+\{\s*(<\d+>(,\s*<\d+>)*)\s*\}/<$nxt>/)
	{
	    my $n = $1;
	    my $args = $2;
	    my @args = map { $_ =~ /<(\d+)>/; $1 } split(/,\s*/,$args);
	    &add_to_encoding($encoding,["of",$n,[@args]]);
	    $got = 1;
	}

	if (! $got) 
	{
	    print STDERR "failed to parse \'$input\'\nGot to \'$s\'\n";
	}
    }
    return ($s =~ /^\s*<(\d+)>\s*$/) ? $1 : undef;
}
	
sub print_bool {
    my($bool) = @_;

    my $s = &printable_bool($bool);
    print $s,"\n";
}

sub printable_bool {
    my($bool) = @_;

    my($nodes,$root) = @$bool;
    my $val = $nodes->[$root];

    if (! ref  $val) 
    { 
	return &printable_bool([$nodes,$val]);
    }
    else
    {
	my $op = $val->[0];

	if ($op eq 'role')
	{
	    return $val->[1];
	}
	elsif ($op eq "of")
	{
	    my @expanded_args = map { &printable_bool([$nodes,$_]) } @{$val->[2]};
	    my $args = join(',',@expanded_args);
	    return "$val->[1] of {$args}";
	}
	elsif ($op eq "not")
	{
	    return "($op " .  &printable_bool([$nodes,$val->[1]]) . ")";
	}
	else
	{
	    return "(" . &printable_bool([$nodes,$val->[1]]) . " $op " . &printable_bool([$nodes,$val->[2]]) . ")";
	}
    }
}

sub add_to_encoding {
    my($encoding,$val) = @_;

    my($mem,$nxt) = @$encoding;
    $mem->[$nxt] = $val;
    $encoding->[1]++;
    return $nxt;
}
    
sub load_roles {
    my($encoding,$abbrev_to_loc,$rolesF) = @_;

    my @roles = ();
    foreach $_ (`cat $rolesF`)
    {
	if ($_ =~ /^(\S+)\t(\S.*\S)/)
	{
	    my($abbrev,$role) = ($1,$2);
	    my $loc = &add_to_encoding($encoding,['role',$role]);
	    $abbrev_to_loc->{$abbrev} = $loc;
	    push(@roles,$role);
	}
    }
    return @roles;
}

sub load_definitions {
    my($encoding,$abbrev_to_loc,$defF) = @_;

    foreach my $def (`cat $defF`)
    {
	if ($def =~ /^(\S+)\t(\S.*\S)/)
	{
	    my($abbrev,$bool) = ($1,$2);
	    my $loc = &parse_bool($bool,$encoding,$abbrev_to_loc);
	    $abbrev_to_loc->{$abbrev} = $loc;
	}
    }
}

sub gather_genes {
    my($fig,$genomeO,$figfams,$role) = @_;
    my($fam_id,$peg,$hit,%found);

#   print STDERR "Gathering for role=$role\n";
    my @fam_ids = $figfams->families_with_functional_role($role);
#   print STDERR "Families for role: ",join(",",@fam_ids),"\n";

    foreach $fam_id (@fam_ids)
    {
	my $figfam = new FigFam($fig,$fam_id);
	my $query;

	foreach $query ($figfam->representatives)
	{
	    foreach $hit ($genomeO->candidate_orfs(-seq => $query))
	    {
#		print STDERR "        candidate=",$hit->get_fid,"\n";
		my $hit_seq = $hit->seq;
		my($ok,undef) = $figfam->should_be_member($hit_seq,undef,1);
 		if ($ok)
		{
#		    print STDERR "             match\n";
		    $found{$hit->get_fid} = $figfam->family_function;
		}
	    }
	}
    }
    return [sort { &FIG::by_fig_id($a->[0],$b->[0]) } map { [$_,$found{$_}] } keys(%found)];
}

sub is_rule_true {
    my($rule,$relevant_genes) = @_;

    my($variant,$exp) = @$rule;
    return &is_true_exp($exp,$relevant_genes) ? $variant : undef;
}

sub is_true_exp {
    my($bool,$relevant_genes) = @_;

    my($nodes,$root) = @$bool;
    my $val = $nodes->[$root];
    if (! ref  $val) 
    { 
	return &is_true_exp([$nodes,$val],$relevant_genes);
    }
    else
    {
	my $op = $val->[0];

	if ($op eq 'role')
	{
	    my $x;
	    return (($x = $relevant_genes->{$val->[1]}) && (@$x > 0)) ? 1 : 0;
	}
	elsif ($op eq "of")
	{
	    my $truth_value;
	    my $count = 0;
	    foreach $truth_value (map { &is_true_exp([$nodes,$_],$relevant_genes) } @{$val->[2]})
	    {
		if ($truth_value) { $count++ }
	    }
	    return $val->[1] <= $count;
	}
	elsif ($op eq "not")
	{
	    return &is_true_exp([$nodes,$val->[1]],$relevant_genes) ? 0 : 1;
	}
	else
	{
	    my $v1 = &is_true_exp([$nodes,$val->[1]],$relevant_genes);
	    my $v2 = &is_true_exp([$nodes,$val->[2]],$relevant_genes);
	    if ($op eq "and") { return $v1 && $v2 };
	    if ($op eq "or")  { return $v1 || $v2 };
	    if ($op eq "->")  { return ((not $v1) || $v2) }
	    else 
	    {
		print STDERR &Dumper($val);
		die "invalid expression";
	    }
	}
    }
}

MCS Webmaster
ViewVC Help
Powered by ViewVC 1.0.3