StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POperl blowing up in sequence alignment by dynamic programming
text
Body
copied!<p>I'm comparing a reference sequence of size 5500 bases and query sequence of size 3600, using dynamic programming (semi global alignment), in fact I don't know much about complexity and performance and the code is blowing up and giving me the error "out of memory". Knowing that it works normally on smaller sequences, my question is: This behavior is normal or I might have another problem in code ?if it's normal any hint to solve this problem ? Thanks in advance.</p> <pre><code>sub semiGlobal { my ( $seq1, $seq2,$MATCH,$MISMATCH,$GAP ) = @_; # initialization: first row to 0 ; my @matrix; $matrix[0][0]{score} = 0; $matrix[0][0]{pointer} = "none"; for ( my $j = 1 ; $j <= length($seq1) ; $j++ ) { $matrix[0][$j]{score} = 0; $matrix[0][$j]{pointer} = "none"; } for ( my $i = 1 ; $i <= length($seq2) ; $i++ ) { $matrix[$i][0]{score} = $GAP * $i; $matrix[$i][0]{pointer} = "up"; } # fill my $max_i = 0; my $max_j = 0; my $max_score = 0; print "seq2: ".length($seq2); print "seq1: ".length($seq1); for ( my $i = 1 ; $i <= length($seq2) ; $i++ ) { for ( my $j = 1 ; $j <= length($seq1) ; $j++ ) { my ( $diagonal_score, $left_score, $up_score ); # calculate match score my $letter1 = substr( $seq1, $j - 1, 1 ); my $letter2 = substr( $seq2, $i - 1, 1 ); if ( $letter1 eq $letter2 ) { $diagonal_score = $matrix[ $i - 1 ][ $j - 1 ]{score} + $MATCH; } else { $diagonal_score = $matrix[ $i - 1 ][ $j - 1 ]{score} + $MISMATCH; } # calculate gap scores $up_score = $matrix[ $i - 1 ][$j]{score} + $GAP; $left_score = $matrix[$i][ $j - 1 ]{score} + $GAP; # choose best score if ( $diagonal_score >= $up_score ) { if ( $diagonal_score >= $left_score ) { $matrix[$i][$j]{score} = $diagonal_score; $matrix[$i][$j]{pointer} = "diagonal"; } else { $matrix[$i][$j]{score} = $left_score; $matrix[$i][$j]{pointer} = "left"; } } else { if ( $up_score >= $left_score ) { $matrix[$i][$j]{score} = $up_score; $matrix[$i][$j]{pointer} = "up"; } else { $matrix[$i][$j]{score} = $left_score; $matrix[$i][$j]{pointer} = "left"; } } # set maximum score if ( $matrix[$i][$j]{score} > $max_score ) { $max_i = $i; $max_j = $j; $max_score = $matrix[$i][$j]{score}; } } } my $align1 = ""; my $align2 = ""; my $j = $max_j; my $i = $max_i; while (1) { if ( $matrix[$i][$j]{pointer} eq "none" ) { $stseq1 = $j; last; } if ( $matrix[$i][$j]{pointer} eq "diagonal" ) { $align1 .= substr( $seq1, $j - 1, 1 ); $align2 .= substr( $seq2, $i - 1, 1 ); $i--; $j--; } elsif ( $matrix[$i][$j]{pointer} eq "left" ) { $align1 .= substr( $seq1, $j - 1, 1 ); $align2 .= "-"; $j--; } elsif ( $matrix[$i][$j]{pointer} eq "up" ) { $align1 .= "-"; $align2 .= substr( $seq2, $i - 1, 1 ); $i--; } } $align1 = reverse $align1; $align2 = reverse $align2; return ( $align1, $align2, $stseq1 ,$max_j); } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload