print "Zugrunde liegende Aehnlichkeitsmatrix"."\n\n";
print " |A  C  G  T | -\n";
print "A|2 -1 -1 -1 |-1\n";
print "C|-1 2 -1 -1 |-1\n";
print "G|-1 -1 2 -1 |-1\n";
print "T|-1 -1 -1 2 |-1\n";
print "-|-1 -1 -1 -1|-1\n";

@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;


print "\n\n\n";
print "  ";
foreach $kiwi(@xSeq)
{
print "$kiwi";
}
print "\n"." ".$LM[0][0];

#### 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";
}
print "\n"."\n"."\n";

#### höchster Wert ####
$Hwert[0]=0;
$e=1;
for ($i=0;$i<=$x;$i++)
{
    for ($j=0;$j<=$y;$j++)
    {
    @Hwert[$e]=$LM[$i][$j];
    $e=$e+1;
    }
}

for ($v=0;$v<$#Hwert;$v++)
{
    if ($Hwert[$v] >= $Hwert[$v+1])
    {
    $Hwert[$v+1]=$Hwert[$v]
    }
else{}
}
$Hochw=$Hwert[$#Hwert];
print $Hwert[$#Hwert];

#### Optimale align ####
for ($i=1;$i<=$x;$i++)
{
$z=0;
    for ($j=1;$j<=$y;$j++)
    {
        if ($Hochw eq $LM[$i][$j])
        {
        $Ugabe=$Hochw;
        $q=$j;
        $w=$i;
            for ($k=0;$k<=10000;$k++)
            {
               
 $abbruch=0;

               
 if ($Ugabe eq $LM[$w-1][$q]-1)
               
 {$qwe=$LM[$w-1][$q]-1;
               
 $align[$z]="-$ySeq[$w-1]|"."1";
               
 $Ugabe=$LM[$w-1][$q];
               
 $z=$z+1;
               
 $w=$w-1;
               
     if ($w eq 0){$k=10000;}else{}
               
 }
               
 else
               
 {
               
 $abbruch=1;
               
 if  (($Ugabe eq $LM[$w-1][$q-1]+2) || ($Ugabe eq $LM[$w-1][$q-1]-1))
               
 {$o=$o+1;
               
 $align[$z]="$xSeq[$q-1]$ySeq[$w-1]|";
               
 $Ugabe=$LM[$w-1][$q-1];
               
 $z=$z+1;
               
 $q=$q-1;
               
 $w=$w-1;
               
     if ($w eq 0){$k=10000;}else{}
               
     if ($q eq 0){$k=10000;}else{}
               
 }else{}
               
 }

               
 if ($Ugabe eq $LM[$w][$q-1]-1)
               
 {
               
 $align[$z]="$xSeq[$q-1]-|"."2";
               
 $Ugabe=$LM[$w][$q-1];
               
 $z=$z+1;
               
 $q=$q-1;
               
     if ($q eq 0){$k=10000;}else{}
               
 }
               
 else
               
 {

               
 if ($abbruch eq 1){}else{
               
 if  (($Ugabe eq $LM[$w-1][$q-1]+2) || ($Ugabe eq $LM[$w-1][$q-1]-1))
               
 {$o=$o+1;
               
 $align[$z]="$xSeq[$w-1]$ySeq[$q-1]|";
               
 $Ugabe=$LM[$w-1][$q-1];
               
 $z=$z+1;
               
 $q=$q-1;
               
 $w=$w-1;
               
     if ($w eq 0){$k=10000;}else{}
               
     if ($q eq 0){$k=10000;}else{}
               
 }else{}}

               
 }


            }
        }
        else{}
    }
}