#!/usr/bin/env perl
#
use List::Util qw[min max];
sub programacion_dinamica{
my($secuencia1,$secuencia2) =@_;
my $len1 =length ($secuencia1);
my $len2 =length($secuencia2);
my @secuencia1 = split("",$secuencia1);
my @secuencia2= split("",$secuencia2);
#Construimos la tabla s y la inicializamos a 0
my @s=();
my @decisiones=();
for (my $i =0; $i <=$len1 ;$i++){
my @ fila_s=();
my @fila_decision=();
for (my $j=0;$j <=$len2;$j++){
push @fila_s,0;
push@fila_decision,'';
print @fila_decision;
}
push @s,\@fila_s; #por referencia
push @decisiones,\@fila_decision;
}
for (my $i =0;$i<$len1;$i++){
$s[0][0]= 0;
$s[$i][0] =$s[$i][0];
$decisiones[$i][0]="abajo";
}
for (my $j=0;$j<=$len2;$j++){
$s[0][$j] =$s[0][$j];
$decisiones[0][$j]="derecha";
}
for (my $j=1;$j<= $len2;$j++){
for (my $i=1;$i<= $len1;$i++){
if ($secuencia1[$i-1] eq $secuencia2[$j-1]){
$suma=1;
}
else{
$suma=0;
}
$s[$i][$j]=max(
$s[$i-1][$j]+0,
$s[$i][$j-1]+0,
$s[$i-1][$j-1]+$suma);
if($s[$i][$j]== $s[$i][$j-1]+0){
$decisiones[$i][$j] ="derecha";
}
elsif ($s[$i][$j]==$s[$i-1][$j-1]+$suma){
$decisiones[$i][$j] ="diagonal";
}
else{
$decisiones[$i][$j]="abajo";
}
}
}
my ($camino_ref, $secuencia_ref) = construir_camino($len1,$len2,\@decisiones,\@secuencia1);
return $s[$len1][$len2], $camino_ref, $secuencia_ref;
}
sub construir_camino{
my ($i, $j, $decisiones_ref, $secuencia1_ref) = @_;
my @camino;
my @secuencia;
while ($i > 0 or $j > 0) {
my $sentido = $decisiones_ref->[$i][$j];
unshift @camino, $sentido;
print "$i:$j: $sentido\n";
if ($sentido eq "abajo") {
$i--;
}
elsif ($sentido eq "derecha") {
$j--;
}
else {
$i--; $j--;
print "$secuencia1_ref->[$i] > @secuencia\n";
unshift @secuencia, $secuencia1_ref->[$i];
}
}
return \@camino, \@secuencia;
}
$secuencia1="ATGCTTA";
$secuencia2="TGCATTAA";
my ($resultado, $camino_ref, $secuencia_ref) = programacion_dinamica($secuencia1,$secuencia2);
print "\n";
print $resultado,"\n";
print join(" ", @$camino_ref), "\n";
print join(" ", @$secuencia_ref), "\n";
Publicado: 2017-01-26 16:07 @713