@xSeq=("A","A","G","G","C","C","T","T");
@ySeq=("A","C","G","T","A","C","T","T");

$LM[0][0]=0;
$x=@xSeq;
$y=@ySeq;

#### x-Achse mit 0 füllen ####
for ($i=1;$i<=$x;$i++)
{
$LM[$i][0]=0;
}

#### y-Achse mit 0 füllen ####
for ($j=1;$j<=$y;$j++)
{
$LM[0][$j]=0;
print $LM[0][$j];
}


print "\n";

for ($i=1;$i<=$x;$i++)
{
print $ySeq[$i-1]."0";
#### wert ermitteln ####
    for ($j=1;$j<=$y;$j++)
    {
    $a=$j-1;
    $s=$i-1;
    if ($xSeq[$a] eq $ySeq[$s])
        {
        $tauscher[0]=$LM[$i-1][$j-1]+2;
        }
        else
        {
        $tauscher[0]=$LM[$i-1][$j-1]-1;
        }
    $tauscher[1]=$LM[$i-1][$j]-1;
    $tauscher[2]=$LM[$i][$j-1]-1;
    $tauscher[3]=-1000;

#### höchsten wert ermitteln ####
    for ($v=0;$v<3;$v++)
    {
        if ($tauscher[$v] > $tauscher[$v+1])
        {
        $tauscher[$v+1]=$tauscher[$v]
        }
        else{}
    }

#### wert einsetzen ####
    if ($tauscher[$v] > 0)
    {
    $LM[$i][$j]=$tauscher[$v];
    }
    else
    {
    $LM[$i][$j]=0
    }

    print $LM[$i][$j];
    }
print "\n";
}

$x = @xSeq = qw (A A G G C C T T);
$y = @ySeq = qw (A C G T A C T T);

$LM[$_][0] = 0 for 0..$x; #### x-Achse mit 0 füllen ####
$LM[0][$_] = 0 for 0..$y; #### y-Achse mit 0 füllen ####

for my $i (1..$x) {
    #### wert ermitteln ####
    for my $j (1..$y) {
        if ($xSeq[$j-1] eq $ySeq[$i-1]) { $tauscher = $LM[$i-1][$j-1] + 2 }
        else                            { $tauscher = $LM[$i-1][$j-1] - 1 }
        #### höchsten wert ermitteln ####
        for ($LM[$i-1][$j]-1, $LM[$i][$j-1]-1, 0) {
            $tauscher = $_ if $_ > $tauscher
        }
        $LM[$i][$j] = $tauscher;
    }
}

$xLength = @xSeq = qw (A A G G C C T T);
$yLength = @ySeq = qw (A C G T A C T T);

$LM[$_][0] = 0 for 0..$xLength; #### x-Achse mit 0 füllen ####
$LM[0][$_] = 0 for 0..$yLength; #### y-Achse mit 0 füllen ####

#### wert ermitteln ####
for my $x (1..$xLength) {
    for my $y (1..$yLength) {
        if ($xSeq[$y-1] eq $ySeq[$x-1]) { $tauscher = $LM[$x-1][$y-1] + 2 }
        else               
             { $tauscher = $LM[$x-1][$y-1] - 1 }
        for ($LM[$x-1][$y]-1, $LM[$x][$y-1]-1, 0) {
            $tauscher = $_ if $_ > $tauscher
        }
        $LM[$x][$y] = $tauscher;
    }
}

#### höchsten Wert finden ####
$Hochw = 0;
for my $x (0..$xLength) {
    for my $y (0..$yLength) {
        if ($Hochw < $LM[$x][$y]) {
            $Hochw = $LM[$x][$y];
            $Hochx = $x;
            $Hochy = $y;
        }
    }
}

#### Optimale align ####
($CursorWert, $x, $y, @align) = ($Hochw, $Hochx, $Hochy);
while() {
    if  (( $CursorWert == $LM[$x-1][$y-1] + 2 ) or
         ( $CursorWert == $LM[$x-1][$y-1] - 1 )    ) {
        $x--;
        $y--;
        push @align, "$xSeq[$x]$ySeq[$y]";
    } elsif ( $CursorWert == $LM[$x-1][$y] - 1 ) {
        $x--;
        push @align, "-$ySeq[$y]";
    } elsif ( $CursorWert == $LM[$x][$y-1] - 1 ) {
        $y--;
        push @align, "$xSeq[$x]-";
    } else { last }
    $CursorWert=$LM[$x][$y];
    last if $x == 0 or $y == 0;
}

print <<EOP;
Zugrunde liegende Aehnlichkeitsmatrix

  | A  C  G  T | -
------------------
A | 2 -1 -1 -1 |-1
C |-1  2 -1 -1 |-1
G |-1 -1  2 -1 |-1
T |-1 -1 -1  2 |-1
------------------
- |-1 -1 -1 -1 |-1
EOP

$" = "";
print "
  @xSeq
 @{$LM[0]}
";
print "$ySeq[$_-1]@{$LM[$_]}
" for 1..$xLength;
print "
$Hochw

";
$" = "|";
print"@align";

use strict;
use warnings;

my $xLength = my @xSeq = qw (A A G G C C T T);
my $yLength = my @ySeq = qw (A C G T A C T T);

my @LM;               
;          #### Längenmatrix
$LM[$_][0] = 0 for 0..$xLength; #### x-Achse mit 0 füllen ####
$LM[0][$_] = 0 for 0..$yLength; #### y-Achse mit 0 füllen ####


#### Längenmatrix berechnen ####
my $tauscher = 0;
for my $x (1..$xLength) {
    for my $y (1..$yLength) {
        if ($xSeq[$x-1] eq $ySeq[$y-1]) { $tauscher = $LM[$x-1][$y-1] + 2 }
        else               
             { $tauscher = $LM[$x-1][$y-1] - 1 }
        for ($LM[$x-1][$y]-1, $LM[$x][$y-1]-1, 0) {
            $tauscher = $_ if $_ > $tauscher
        }
        $LM[$x][$y] = $tauscher;
    }
}

#### höchsten Wert finden ####
my ($Hochw, $Hochx, $Hochy) = (0, 0, 0);
for my $x (0..$xLength) {
    for my $y (0..$yLength) {
        if ($Hochw < $LM[$x][$y]) {
            $Hochw = $LM[$x][$y];
            $Hochx = $x;
            $Hochy = $y;
        }
    }
}

#### Wegematrix berechnen ####
my @WM;               
;          #### Wegematrix
my @WStack = ([$Hochx, $Hochy]);#### Wegestack
my ($w, $x, $y, $z);
while (@WStack) {
    ($x, $y) = @{pop @WStack};
    next if $WM[$x][$y];
    $z = $LM[$x][$y];
    $w = 0;
    if  (    (( $z == $LM[$x-1][$y-1] + 2 ) or ( $z == $LM[$x-1][$y-1] - 1 ))
         and ($x > 1 and $y > 1)              &nbs

p;              &nbs

p;            ) {
        $w |= 1;
        push @WStack, [$x-1, $y-1];
    }
    if ( $z == $LM[$x-1][$y] - 1 ) {
        $w |= 2;
        push @WStack, [$x-1, $y];
    }
    if ( $z == $LM[$x][$y-1] - 1 ) {
        $w |= 4;
        push @WStack, [$x, $y-1];
    }
    $WM[$x][$y] = $w;
}

#### Optimalen Pfad (align) ####
($x, $y) = ($Hochx, $Hochy);
my @oPfad = ($xSeq[$x-1].$ySeq[$y-1]) ; 
while ($WM[$x][$y]) {
    $w = $WM[$x][$y];
    if    ($w & 0b001) { unshift @oPfad, $xSeq[--$x-1].$ySeq[--$y-1] }
    elsif ($w & 0b010) { unshift @oPfad, $xSeq[--$x-1]."-"           }
    elsif ($w & 0b100) { unshift @oPfad,           "-".$ySeq[--$y-1] }
}

#### allePfade ####
my (@allePfade, @CPfad, @abzw);    #### Pfade, aktueller Pfad(cursor), Abzweigungen
my @PQueue = ([$Hochx, $Hochy, $xSeq[$Hochx-1].$ySeq[$Hochy-1]]);
while (@PQueue) {
    ($x, $y, @CPfad) = @{shift @PQueue};
    while ($WM[$x][$y]){
        $w = $WM[$x][$y];
             @abzw = ();
        push @abzw, [$x-1, $y-1, $xSeq[$x-2].$ySeq[$y-2]] if $w & 0b001;
        push @abzw, [$x-1, $y  , $xSeq[$x-2]."-"        ] if $w & 0b010;
        push @abzw, [$x  , $y-1,         "-".$ySeq[$y-2]] if $w & 0b100;
        push @PQueue, [@{$abzw[$_]}, @CPfad ] for 1 .. $#abzw;
        unshift @CPfad, $abzw[0][2];
        ($x, $y) = @{$abzw[0]};
    }
    push @allePfade, [@CPfad];
}

# Ausgabe :
print <<EOP;

Zugrunde liegende Aehnlichkeitsmatrix:

  | A  C  G  T | -
------------------
A | 2 -1 -1 -1 |-1
C |-1  2 -1 -1 |-1
G |-1 -1  2 -1 |-1
T |-1 -1 -1  2 |-1
------------------
- |-1 -1 -1 -1 |-1
EOP

$" = "";
print "\n  @ySeq\n @{$LM[0]}\n";
print "$xSeq[$_-1]@{$LM[$_]}\n" for 1..$xLength;
print "\nHochwert: $Hochw\n\n";
$" = "|";
print "1 opt. Pfad: @oPfad\n\nAlle Pfade:\n\n";
print "@{@allePfade[$_]}\n" for 0..$#allePfade;