[Bio] / Sprout / SHSigGenes.pm Repository:
ViewVC logotype

Annotation of /Sprout/SHSigGenes.pm

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.13 - (view) (download) (as text)

1 : parrello 1.1 #!/usr/bin/perl -w
2 :    
3 :     package SHSigGenes;
4 :    
5 :     use strict;
6 :     use Tracer;
7 :     use SearchHelper;
8 :     use CGI;
9 :     use HTML;
10 :     use Sprout;
11 : parrello 1.10 use Time::HiRes;
12 : parrello 1.11 use FIGRules;
13 : parrello 1.1
14 :     our @ISA = qw(SearchHelper);
15 :    
16 :     =head1 Gene Discrimination Feature Search Helper
17 :    
18 :     =head2 Introduction
19 :    
20 :     This search performs a signature genes comparison. The user selects two genome sets,
21 :     and the search returns genes from a given genome which are common only in the first set
22 :     and not in the second. If the second set is empty, the search will return genes from
23 :     the given genome that are common in the first set.
24 :    
25 :     Gene identity will be computed in this case using bidirectional best hits. If gene X
26 :     from the given genome has a BBH in a specified genome Y, then it is said to occur
27 :     in whatever set includes genome Y. A gene is considered I<common> if it occurs in a
28 :     certain percentage of the genomes of the set.
29 :    
30 :     This search has the following extra parameters.
31 :    
32 :     =over 4
33 :    
34 :     =item given
35 :    
36 :     The ID of the given genome.
37 :    
38 :     =item target[]
39 :    
40 :     The IDs of the genomes in the first (target) set. The given genome is
41 :     automatically considered a part of this set, so it can never be empty.
42 :    
43 :     =item exclusion[]
44 :    
45 :     The IDs of the genomes in the second (exclusion) set. If this set is empty, then
46 :     no genes will be considered common in set 2, causing all genes common in set 1
47 :     to be selected.
48 :    
49 :     =item commonality
50 :    
51 :     Minimum score for a gene to be considered common. The score is equal to the number
52 :     of genomes containing a bidirectional best hit of the gene divided by the total
53 :     number of genomes. The default is C<0.8>. A value of C<1> means a gene must have
54 :     BBHs in all of the genomes to be considered common; a value of C<0> is invalid.
55 :    
56 :     =item cutoff
57 :    
58 :     Maximum match difference for a BBH hit to be considered valid. The default is C<1e-10>.
59 :    
60 : parrello 1.11 =item showMatch
61 :    
62 :     If TRUE, then all the genes in the target set that match the ones in the reference genome
63 :     will be shown in an extra column.
64 :    
65 : parrello 1.1 =back
66 :    
67 :     =head2 Virtual Methods
68 :    
69 :     =head3 Form
70 :    
71 : parrello 1.7 C<< my $html = $shelp->Form(); >>
72 : parrello 1.1
73 :     Generate the HTML for a form to request a new search.
74 :    
75 :     =cut
76 :    
77 :     sub Form {
78 :     # Get the parameters.
79 :     my ($self) = @_;
80 :     # Get the CGI and sprout objects.
81 :     my $cgi = $self->Q();
82 :     my $sprout = $self->DB();
83 :     # Start the form.
84 :     my $retVal = $self->FormStart("Signature Genes");
85 :     # The bulk of this form will be two genome selection menus, one for the first
86 :     # (target) set and one for the second (exclusion) set. Above these two controls
87 :     # there is the selector for the given genome, the commonality and cutoff values,
88 :     # and the submit button. Our first task, then, is to get the genome selection
89 :     # menus.
90 : parrello 1.5 my $givenMenu = $self->NmpdrGenomeMenu('given', 0, [$cgi->param('given')]);
91 : parrello 1.4 my $targetMenu = $self->NmpdrGenomeMenu('target', 'multiple', [$cgi->param('target')], 10, 'exclusion');
92 :     my $excludeMenu = $self->NmpdrGenomeMenu('exclusion', 'multiple', [$cgi->param('exclusion')], 10, 'target');
93 : parrello 1.1 # Get the default values to use for the commonality and cutoff controls.
94 :     my $commonality = $cgi->param('commonality') || "0.8";
95 :     my $cutoff = $cgi->param('cutoff') || "1e-10";
96 : parrello 1.6 my $statistical = $cgi->param('statistical') || 1;
97 : parrello 1.11 my $showMatch = $cgi->param('showMatch') || 0;
98 : parrello 1.12 my $useSims = $cgi->param('useSims') || 0;
99 : parrello 1.13 my $pegsOnly = $cgi->param('pegsOnly') || 1;
100 : parrello 1.9 # Now we build the table rows.
101 : parrello 1.1 my @rows = ();
102 : parrello 1.9 # First we have the given genome.
103 :     push @rows, $cgi->Tr($cgi->td({valign => "top"}, "Reference Genome"),
104 :     $cgi->td({colspan => 2}, $givenMenu));
105 :     # Now show the target and exclusion menus.
106 :     push @rows, $cgi->Tr($cgi->td({valign => "top"}, "Inclusion Genomes (Set 1)"),
107 :     $cgi->td({colspan => 2}, $targetMenu));
108 :     push @rows, $cgi->Tr($cgi->td({valign => "top"}, "Exclusion Genomes (Set 2)"),
109 :     $cgi->td({colspan => 2}, $excludeMenu));
110 : parrello 1.12 # Next, the tuning parameters.
111 : parrello 1.1 push @rows, $cgi->Tr($cgi->td("Commonality"),
112 :     $cgi->td($cgi->textfield(-name => 'commonality',
113 :     -value => $commonality,
114 : parrello 1.9 -size => 5))),
115 : parrello 1.11 $cgi->Tr($cgi->td(), $cgi->td(join(" ",
116 : parrello 1.5 $cgi->checkbox(-name => 'statistical',
117 :     -checked => $statistical,
118 :     -value => 1,
119 : parrello 1.12 -label => 'Use Statistical Algorithm'),
120 :     $cgi->checkbox(-name => 'useSims',
121 :     -checked => $useSims,
122 :     -value => 1,
123 :     -label => 'Use Similarities')))),
124 :     $cgi->Tr($cgi->td(), $cgi->td(join(" ",
125 : parrello 1.11 $cgi->checkbox(-name => 'showMatch',
126 :     -checked => $showMatch,
127 :     -value => 1,
128 : parrello 1.12 -label => 'Show Matching Genes'),
129 : parrello 1.13 # $cgi->checkbox(-name => 'pegsOnly',
130 :     # -checked => $pegsOnly,
131 :     # -value => 1,
132 :     # -label => 'PEGs Only')
133 :     ))),
134 : parrello 1.12 $cgi->Tr($cgi->td("Cutoff"),
135 : parrello 1.1 $cgi->td($cgi->textfield(-name => 'cutoff',
136 :     -value => $cutoff,
137 :     -size => 5)));
138 : parrello 1.9 # Next, the feature filter rows.
139 :     push @rows, $self->FeatureFilterRows();
140 :     # Finally, the submit button.
141 : parrello 1.1 push @rows, $self->SubmitRow();
142 :     # Create the table.
143 :     $retVal .= $self->MakeTable(\@rows);
144 :     # Close the form.
145 :     $retVal .= $self->FormEnd();
146 :     # Return the result.
147 :     return $retVal;
148 :     }
149 :    
150 :     =head3 Find
151 :    
152 :     C<< my $resultCount = $shelp->Find(); >>
153 :    
154 :     Conduct a search based on the current CGI query parameters. The search results will
155 :     be written to the session cache file and the number of results will be
156 :     returned. If the search parameters are invalid, a result count of C<undef> will be
157 :     returned and a result message will be stored in this object describing the problem.
158 :    
159 :     =cut
160 :    
161 :     sub Find {
162 :     # Get the parameters.
163 :     my ($self) = @_;
164 :     # Get the sprout and CGI query objects.
165 :     my $cgi = $self->Q();
166 :     my $sprout = $self->DB();
167 : parrello 1.2 # Declare the return variable. If it remains undefined, the caller will
168 :     # assume there was an error.
169 : parrello 1.1 my $retVal;
170 : parrello 1.11 # Denote the extra columns go at the end.
171 :     $self->SetExtraPos(1);
172 : parrello 1.10 # Create the timers.
173 :     my ($saveTime, $loopCounter, $bbhTimer, $putTimer, $queryTimer) = (0, 0, 0, 0, 0);
174 : parrello 1.2 # Validate the numeric parameters.
175 :     my $commonality = $cgi->param('commonality');
176 :     my $cutoff = $cgi->param('cutoff');
177 : parrello 1.13 my $pegsOnly = $cgi->param('pegsOnly') || 1;
178 : parrello 1.2 if ($commonality !~ /^\s*\d(\.\d+)?\s*$/) {
179 :     $self->SetMessage("Commonality value appears invalid, too big, negative, or not a number.");
180 :     } elsif ($commonality <= 0 || $commonality > 1) {
181 :     $self->SetMessage("Commonality cannot be 0 and cannot be greater than 1.");
182 :     } elsif ($cutoff !~ /^\s*\d(.\d+)?(e\-\d+)?\s*$/) {
183 :     $self->SetMessage("Cutoff must be an exponential number (e.g. \"1e-20\" or \"2.5e-11\".");
184 :     } elsif ($cutoff > 1) {
185 :     $self->SetMessage("Cutoff cannot be greater than 1.");
186 :     } else {
187 :     # Now we need to gather and validate the genome sets.
188 : parrello 1.12 $self->PrintLine("Gathering the target genomes. ");
189 : parrello 1.3 my ($givenGenomeID) = $self->GetGenomes('given');
190 :     my %targetGenomes = map { $_ => 1 } $self->GetGenomes('target');
191 : parrello 1.12 $self->PrintLine("Gathering the exclusion genomes. ");
192 : parrello 1.3 my %exclusionGenomes = map { $_ => 1 } $self->GetGenomes('exclusion');
193 : parrello 1.12 $self->PrintLine("Validating the genome sets.<br />");
194 : parrello 1.2 # Insure the given genome is not in the exclusion set.
195 :     if ($exclusionGenomes{$givenGenomeID}) {
196 :     $self->SetMessage("The given genome ($givenGenomeID) cannot be in the exclusion set.");
197 :     } else {
198 :     # Insure the given genome is in the target set.
199 :     $targetGenomes{$givenGenomeID} = 1
200 :     }
201 : parrello 1.5 # Find out if we want to use a statistical analysis.
202 : parrello 1.11 my $statistical = $cgi->param('statistical') || 1;
203 :     # Find out if we need to show matching genes.
204 :     my $showMatch = $cgi->param('showMatch') || 0;
205 : parrello 1.2 # Denote we have not yet found any genomes.
206 :     $retVal = 0;
207 : parrello 1.10 # Compute the list of genomes of interest.
208 :     my @allGenomes = (keys %exclusionGenomes, keys %targetGenomes);
209 : parrello 1.12 # Set the parameter that indicates whether or not we're in PEGs-only mode.
210 :     my $pegMode = ($pegsOnly ? 'peg' : undef);
211 :     # Get the peg matrix.
212 :     Trace("Requesting matrix.") if T(3);
213 : parrello 1.10 $saveTime = time();
214 : parrello 1.12 my %bbhMatrix;
215 :     if (! $cgi->param('useSims')) {
216 :     # Here we are using BBHs, which are fast enough to do in one gulp.
217 :     $self->PrintLine("Requesting bidirectional best hits. ");
218 :     %bbhMatrix = $sprout->BBHMatrix($givenGenomeID, $cutoff, @allGenomes);
219 :     } else {
220 :     # Here we are using similarities, which is much more complicated.
221 :     $self->PrintLine("Requesting similarities.<br />");
222 :     # Create a filtering matrix for the results. We only want to keep PEGs in the
223 :     # specified target and exclusion genomes.
224 :     my %keepGenomes = map { $_ => 1 } @allGenomes;
225 :     # Loop through the given genome's features.
226 :     my @features = $sprout->FeaturesOf($givenGenomeID, $pegMode);
227 :     for my $fid (@features) {
228 :     $self->PrintLine("Retrieving similarities for $fid. ");
229 :     # Get this feature's similarities.
230 :     my $simList = $sprout->Sims($fid, 1000, $cutoff, 'fig');
231 :     my $simCount = scalar @{$simList};
232 :     $self->PrintLine("Raw similarity count: $simCount. ");
233 :     # Create the matrix hash for this feature.
234 :     $bbhMatrix{$fid} = {};
235 :     # Now we need to filter out the similarities that don't land on the target genome.
236 :     $simCount = 0;
237 :     for my $sim (@{$simList}) {
238 :     # Insure this similarity lands on a target genome.
239 :     my ($genomeID2) = FIGRules::ParseFeatureID($sim->id2);
240 :     if ($keepGenomes{$genomeID2}) {
241 :     # Here we're keeping the similarity, so we put it in this feature's hash.
242 :     $bbhMatrix{$fid}->{$sim->id2} = $sim->psc;
243 :     $simCount++;
244 :     }
245 :     }
246 :     $self->PrintLine("Similarities retained: $simCount.<br />");
247 :     }
248 :     }
249 : parrello 1.10 $bbhTimer += time() - $saveTime;
250 : parrello 1.12 $self->PrintLine("Time to build matrix: $bbhTimer seconds.<br />");
251 :     Trace("Matrix built.") if T(3);
252 : parrello 1.4 # Create a feature query object to loop through the chosen features of the given
253 :     # genome.
254 : parrello 1.10 Trace("Creating feature query.") if T(3);
255 :     $saveTime = time();
256 : parrello 1.4 my $fquery = FeatureQuery->new($self, $givenGenomeID);
257 : parrello 1.10 $queryTimer += time() - $saveTime;
258 : parrello 1.4 # Get the sizes of the two sets. This information is useful in computing commonality.
259 :     my $targetSetSize = scalar keys %targetGenomes;
260 :     my $exclusionSetSize = scalar keys %exclusionGenomes;
261 :     # Loop through the features.
262 : parrello 1.10 my $done = 0;
263 :     while (! $done) {
264 :     # Get the next feature.
265 :     $saveTime = time();
266 :     my $record = $fquery->Fetch();
267 :     $queryTimer += time() - $saveTime;
268 :     if (! $record) {
269 :     $done = 1;
270 :     } else {
271 :     # Get the feature's ID.
272 :     my $fid = $fquery->FID();
273 : parrello 1.12 # Insure we want to look at this feature.
274 :     if ($fid =~ /\.peg\./ || ! $pegsOnly) {
275 :     Trace("Checking feature $fid.") if T(4);
276 :     $self->PrintLine("Checking feature $fid.<br />");
277 :     # Get its list of BBHs. The list is actually a hash mapping each BBH to its
278 :     # score. All we care about, however, are the BBHs themselves.
279 :     my $bbhList = $bbhMatrix{$fid};
280 :     # We next wish to loop through the BBH IDs, counting how many are in each of the
281 :     # sets. If a genome occurs twice, we only want to count the first occurrence, so
282 :     # we have a hash of genomes we've already seen. The hash will map each gene ID
283 :     # to 0, 1, or 2, depending on whether it was found in the reference genome,
284 :     # a target genome, or an exclusion genome.
285 :     my %alreadySeen = ();
286 :     # Save the matching genes in here.
287 :     my %genesMatching = ();
288 :     # Clear the exclusion count.
289 :     my $exclusionCount = 0;
290 :     # Denote that we're in our own genome.
291 :     $alreadySeen{$givenGenomeID} = 0;
292 :     my $targetCount = 1;
293 :     # Loop through the BBHs/Sims.
294 :     for my $bbhPeg (keys %{$bbhList}) {
295 :     # Get the genome ID. We want to find out if this genome is new.
296 :     my ($genomeID) = FIGRules::ParseFeatureID($bbhPeg);
297 :     if (! exists $alreadySeen{$genomeID}) {
298 :     # It's new, so we check to see which set it's in.
299 :     if ($targetGenomes{$genomeID}) {
300 :     # It's in the target set.
301 :     $targetCount++;
302 :     $alreadySeen{$genomeID} = 1;
303 :     } elsif ($exclusionGenomes{$genomeID}) {
304 :     # It's in the exclusion set.
305 :     $exclusionCount++;
306 :     $alreadySeen{$genomeID} = 2;
307 :     }
308 :     # Note that $alreadySeen{$genomeID} exists in the hash by this
309 :     # point. If it's 1, we need to save the current PEG.
310 :     if ($alreadySeen{$genomeID} == 1) {
311 :     $genesMatching{$bbhPeg} = 1;
312 :     }
313 : parrello 1.11 }
314 : parrello 1.12 }
315 :     # Create a variable to indicate whether or not we want to keep this feature and
316 :     # another for the score.
317 :     my ($okFlag, $score);
318 :     # We need to see if we're using statistics or not. This only matters
319 :     # for a two-set situation.
320 :     if ($statistical && $exclusionSetSize > 0) {
321 :     # This is the magic formula for choosing the differentiating genes. It looks like
322 :     # it has something to do with variance computations, but I'm not sure.
323 :     my $targetNotCount = $targetSetSize - $targetCount;
324 :     my $targetSquare = $targetCount * $targetCount + $targetNotCount * $targetNotCount;
325 :     my $exclusionNotCount = $exclusionSetSize - $exclusionCount;
326 :     my $exclusionSquare = $exclusionCount * $exclusionCount + $exclusionNotCount * $exclusionNotCount;
327 :     my $mixed = $targetCount * $exclusionCount + $targetNotCount * $exclusionNotCount;
328 :     my $inD = 1 - (($exclusionSetSize * $mixed) / ($targetSetSize * $exclusionSquare));
329 :     my $outD = 1 - (($targetSetSize * $mixed) / ($exclusionSetSize * $targetSquare));
330 :     # If the two differentials are greater than one, we keep this feature.
331 :     $score = $inD + $outD;
332 :     $okFlag = ($score > 1);
333 :     # Subtract 1 from the score so it looks like the commonality score.
334 :     $score -= 1.0;
335 :     } else {
336 :     # Check to see if we're common in set 1 and not in set 2.
337 :     my $score1 = IsCommon($targetCount, $targetSetSize, $commonality);
338 :     my $score2 = IsCommon($exclusionCount, $exclusionSetSize, $commonality);
339 :     if ($score1 && ! $score2) {
340 :     # We satisfy the criterion, so we put this feature to the output. The
341 :     # score is essentially $score1, since $score2 is zero.
342 :     $score = $score1;
343 :     $okFlag = 1;
344 : parrello 1.10 }
345 :     }
346 : parrello 1.12 if ($okFlag) {
347 :     # Put this feature to the output. We have one or two extra columns.
348 :     # First we store the score.
349 :     $fquery->AddExtraColumns(score => sprintf("%.3f",$score));
350 :     # Next we add the list of matching genes, but only if "showMatch" is specified.
351 :     if ($showMatch) {
352 :     # The matching genes are in the hash "genesMatching".
353 :     my @genes = sort { FIGRules::FIGCompare($a,$b) } keys %genesMatching;
354 :     # We need to linkify them.
355 :     my $genesHTML = join(", ", map { HTML::fid_link($cgi, $_) } @genes);
356 :     # Now add them as an extra column.
357 :     $fquery->AddExtraColumns(matches => $genesHTML);
358 :     }
359 :     $saveTime = time();
360 :     $self->PutFeature($fquery);
361 :     $putTimer += time() - $saveTime;
362 :     # Increase the result count.
363 :     $retVal++;
364 : parrello 1.4 }
365 : parrello 1.12 # Check for a timer trace. We trace every 500 features.
366 :     $loopCounter++;
367 :     if (T(3) && $loopCounter % 500 == 0) {
368 :     Trace("Time spent for $loopCounter features: Put = $putTimer, Query = $queryTimer, BBH = $bbhTimer.");
369 : parrello 1.11 }
370 : parrello 1.5 }
371 :     }
372 : parrello 1.4 }
373 : parrello 1.5 # Close the session file.
374 : parrello 1.10 $saveTime = time();
375 : parrello 1.5 $self->CloseSession();
376 : parrello 1.10 $putTimer += time() - $saveTime;
377 : parrello 1.2 }
378 : parrello 1.10 # Trace the timers.
379 :     Trace("Time spent: Put = $putTimer, Query = $queryTimer, BBH = $bbhTimer.") if T(3);
380 : parrello 1.1 # Return the result count.
381 :     return $retVal;
382 :     }
383 :    
384 :     =head3 Description
385 :    
386 :     C<< my $htmlText = $shelp->Description(); >>
387 :    
388 :     Return a description of this search. The description is used for the table of contents
389 :     on the main search tools page. It may contain HTML, but it should be character-level,
390 :     not block-level, since the description is going to appear in a list.
391 :    
392 :     =cut
393 :    
394 :     sub Description {
395 :     # Get the parameters.
396 :     my ($self) = @_;
397 :     # Return the result.
398 : parrello 1.8 return "Search for genes that are common to a group of organisms or that discriminate between two groups of organisms.";
399 : parrello 1.1 }
400 :    
401 : parrello 1.4 =head2 Internal Utilities
402 :    
403 :     =head3 IsCommon
404 :    
405 : parrello 1.11 C<< my $score = SHSigGenes::IsCommon($count, $size, $commonality); >>
406 : parrello 1.4
407 : parrello 1.11 Return the match score if a specified count indicates a gene is common in a specified set
408 :     and 0 otherwise. Commonality is computed by dividing the count by the size of the set and
409 : parrello 1.4 comparing the result to the minimum commonality ratio. The one exception is
410 : parrello 1.11 if the set size is 0. In that case, this method always returns 0.
411 : parrello 1.4
412 :     =over 4
413 :    
414 :     =item count
415 :    
416 :     Number of elements of the set that have the relevant characteristic.
417 :    
418 :     =item size
419 :    
420 :     Total number of elements in the set.
421 :    
422 :     =item commonality
423 :    
424 :     Minimum count/size ratio for the characteristic to be considered common.
425 :    
426 :     =item RETURN
427 :    
428 :     Returns TRUE if the characteristic is common, else FALSE.
429 :    
430 :     =back
431 :    
432 :     =cut
433 :    
434 :     sub IsCommon {
435 :     # Get the parameters.
436 :     my ($count, $size, $commonality) = @_;
437 :     # Declare the return variable.
438 :     my $retVal = 0;
439 :     # Only procced if the size is positive.
440 :     if ($size > 0) {
441 : parrello 1.11 # Compute the commonality.
442 :     $retVal = $count/$size;
443 :     # If it's too small, clear it.
444 :     if ($retVal < $commonality) {
445 :     $retVal = 0;
446 :     }
447 : parrello 1.4 }
448 :     # Return the result.
449 :     return $retVal;
450 :     }
451 :    
452 : parrello 1.1 1;

MCS Webmaster
ViewVC Help
Powered by ViewVC 1.0.3