Exon Chaining source code in Perl (Dynamic programming)

Exon Chaining Problem:
Can't tell lucky or not the same problem is can be found in Uva online judge for programming.When our team attend a contest in a university in bangladesh this modified version of this problem is given.(11908 Skyscraper).
In Bio-informatics it is a set of exon is given now create the amino acid from which the needed protein can be found.
Input >> here cuttings from start to end with score is given.
Output >> Give the maximum Allginment Score and selected chunk.

Code is given bellow (perl):
*************************************************************************************
INPUT >>
2 3 3
1 5 5
4 8 6
6 12 10
9 10 1
7 17 12
11 15 7
13 14 0
16 18 4
OUTPUT>>
21

use strict;
use warnings;

main(@ARGV);

sub main
{
  my $line;
  my $co = 0;
  my ($i,$ans);
  open(MYDATA,"in1.txt");
  my @G = [(1...10),(1...4)];
  while($line = <MYDATA>)
  {
    chomp($line);
    my @p = split' ',$line;
    for($i=0;$i<3;$i++)
    {
      $G[$co][$i] = $p[$i];
    }
    ++$co;
  }
  close(MYDATA);
  #print $G[1][1];
 
  $ans = exon(\@G,$co);
  print $ans,"\n";

}


sub exon

   my($g,$n) = @_;
   my @G = @{$g};
   my ($i,@s);
 
   for($i=0;$i<=$n*2;$i++)
   {
     $s[$i] = 0;
   }
  
   for($i=1;$i<=2*$n;$i++)
   {
      my($fl,$ro,$cos) = root(\@G,$i,$n);
  
      if($fl == 1)
      {
        if($s[$ro] + $cos > $s[$i-1])
        {
          $s[$i] = $s[$ro] + $cos;
        }
        else
        {
            $s[$i] = $s[$i-1] ;
        }
     
      }
      else
      {
        $s[$i] = $s[$i-1];
      }
  
   }
  
   return $s[$n*2];

}

sub root
{

  my($g,$m,$lim) = @_;
  my @G = @{$g};
  my $i;

  for($i=0;$i<$lim;$i++)
  {
    if($G[$i][1] == $m)
    {
      return (1,$G[$i][0],$G[$i][2]);
    }
  } 
  return (0,-1,-1);
}

Post a Comment