Introduction to Bioinformatics Algorithm Partial Digest source code in Perl

Partial Digest Problem :
Its a common known problem in bio-informatics where chunk of DNA with deferent length is given.Our work is to find out in what position this chunk is cut-up.I completed this problem by backtracking in Perl language where multiple solution can be found.The code is given here.You should first understand the problem than use this code.(For your good)I use Introduction to Bio-informatics Algorithm Book as reference.

*************************************************************************************


use strict;
use warnings;

main(@ARGV);

sub main
{

    # here value is the  set of piece which cut from entire length  and flag use for just check which piece used and which
    # piece not used before and unsed is counter for how much piece are not  used still now , inti is the starting point and
    # end is end point of entire length  and at the end point are the array which contain still now how much point we have
    # and whose are they, for  every dfs function or subrutine have  the necessary information to get the solution and it also
    # able to find multiple solution because it always main base case a trach its possible way

    my @value = (2,2,3,3,4,5,6,7,8);
    my @flag = (0,0,0,0,0,0,0,0,0);
    my @points ;
    push(@points,0);
    push(@points,10);
    my $unused  = 9;
    my $inti = 0;
    my $end = 10;
    dfs(\@value,\@points,\@flag,$unused,$inti,$end);

}


sub dfs
{

    my ($temp_value,$temp_points,$temp_flag,$unused,$inti,$end) = @_;
    my @value = @{$temp_value};
    my @points = @{$temp_points};
    my @flag = @{$temp_flag};
    my $current_point = 0 ;my $i;my $j;my $k;my $len;my $len2;my $cur;my $cnt ; my $check;
   
   
    # unused ==0 is the base case for the backtrack , here i know for every state we have only two candidate
    # so if we code two dfs one after another then we can handle this  easily so below i did this
   
    if($unused==0)
    {   
        print "here found a solution \n";
        @points = sort(@points);
        print "@points\n";
    }
   
    else
    {
   
        $len = scalar @value;
        for($i=$len-1; $i>=0;--$i)
        {
            if($flag[$i]==0)
            {
                $cur=$value[$i];
                last;
            }
        }
       
        $current_point =  $end - $cur;

        $cnt=0;
        $len= scalar @points;
        $len2=scalar @value;
        for($i=0;$i<$len;++$i)
        {
            $check = 0;
            for($j=0;$j<$len2;++$j)
            {
                if( (abs($current_point-$points[$i])==$value[$j]) && $flag[$j]==0)
                {
                    $check=1;
                    last;
                }
            }
            if($check==1)
            {
                ++$cnt;
            }
        }
       
        if($cnt==$len)
        {
       
            my @ommit;
            $len= scalar @points;
            $len2=scalar @value;
            for($i=0;$i<$len;++$i)
            {
                for($j=0;$j<$len2;++$j)
                {
                    if( (abs($current_point-$points[$i])==$value[$j]) && $flag[$j]==0)
                    {
                        $flag[$j]=1;
                        push(@ommit,$value[$j]);
                        last;
                    }
                }
            }
           
           
            #first dfs;
           
            push(@points,$current_point);
            dfs(\@value,\@points,\@flag,$unused-$len,$inti,$end);
            pop(@points);
           
           
            $len= scalar @ommit;
            $len2=scalar @value;
            for($i=0;$i<$len;++$i)
            {
                for($j=0;$j<$len2;++$j)
                {
                    if( $ommit[$i]==$value[$j] && $flag[$j]==1)
                    {
                        $flag[$j]=0;
                        last;
                    }
                }
            }
        }
       
       
        $current_point = $cur;
        $cnt=0;
        $len= scalar @points;
        $len2=scalar @value;
        for($i=0;$i<$len;++$i)
        {
            $check = 0;
            for($j=0;$j<$len2;++$j)
            {
                if( (abs($current_point-$points[$i])==$value[$j]) && $flag[$j]==0)
                {
                    $check = 1;
                    last;
                }
            }
            if($check==1)
            {
                ++$cnt;
            }
        }
       
        if($cnt==$len)
        {
           
            my @ommit;
            $len= scalar @points;
            $len2=scalar @value;
            for($i=0;$i<$len;++$i)
            {
                for($j=0;$j<$len2;++$j)
                {
                    if( (abs($current_point-$points[$i])==$value[$j]) && $flag[$j]==0)
                    {
                        $flag[$j]=1;
                        push(@ommit,$value[$j]);
                        last;
                    }
                }
            }
           
           
            # second dfs ;
           
            push(@points,$current_point);
            dfs(\@value,\@points,\@flag,$unused-$len,$inti,$end);
            pop(@points);
           
            $len= scalar @ommit;
            $len2=scalar @value;
            for($i=0;$i<$len;++$i)
            {
                for($j=0;$j<$len2;++$j)
                {
                    if( $ommit[$i]==$value[$j] && $flag[$j]==1)
                    {
                        $flag[$j]=0;
                        last;
                    }
                }
            }
        }
    }

}




Post a Comment