#!/usr/bin/perl
#You may distribute and modify this file following the terms of WTFPL 2.0
@r = qw/A  R  N  D  C  Q  E  G  H  I  L  K  M  F  P  S  T  W  Y  V  B  Z  X -/;
for (split "\n",
'A 4 -1 -2 -2  0 -1 -1  0 -2 -1 -1 -1 -1 -2 -1  1  0 -3 -2  0 -2 -1  0 -4 
R -1  5  0 -2 -3  1  0 -2  0 -3 -2  2 -1 -3 -2 -1 -1 -3 -2 -3 -1  0 -1 -4 
N -2  0  6  1 -3  0  0  0  1 -3 -3  0 -2 -3 -2  1  0 -4 -2 -3  3  0 -1 -4 
D -2 -2  1  6 -3  0  2 -1 -1 -3 -4 -1 -3 -3 -1  0 -1 -4 -3 -3  4  1 -1 -4 
C  0 -3 -3 -3  9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1 -3 -3 -2 -4 
Q -1  1  0  0 -3  5  2 -2  0 -3 -2  1  0 -3 -1  0 -1 -2 -1 -2  0  3 -1 -4 
E -1  0  0  2 -4  2  5 -2  0 -3 -3  1 -2 -3 -1  0 -1 -3 -2 -2  1  4 -1 -4 
G  0 -2  0 -1 -3 -2 -2  6 -2 -4 -4 -2 -3 -3 -2  0 -2 -2 -3 -3 -1 -2 -1 -4 
H -2  0  1 -1 -3  0  0 -2  8 -3 -3 -1 -2 -1 -2 -1 -2 -2  2 -3  0  0 -1 -4 
I -1 -3 -3 -3 -1 -3 -3 -4 -3  4  2 -3  1  0 -3 -2 -1 -3 -1  3 -3 -3 -1 -4 
L -1 -2 -3 -4 -1 -2 -3 -4 -3  2  4 -2  2  0 -3 -2 -1 -2 -1  1 -4 -3 -1 -4 
K -1  2  0 -1 -3  1  1 -2 -1 -3 -2  5 -1 -3 -1  0 -1 -3 -2 -2  0  1 -1 -4 
M -1 -1 -2 -3 -1  0 -2 -3 -2  1  2 -1  5  0 -2 -1 -1 -1 -1  1 -3 -1 -1 -4 
F -2 -3 -3 -3 -2 -3 -3 -3 -1  0  0 -3  0  6 -4 -2 -2  1  3 -1 -3 -3 -1 -4 
P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4  7 -1 -1 -4 -3 -2 -2 -1 -2 -4 
S  1 -1  1  0 -1  0  0  0 -1 -2 -2  0 -1 -2 -1  4  1 -3 -2 -2  0  0  0 -4 
T  0 -1  0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1  1  5 -2 -2  0 -1 -1  0 -4 
W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1  1 -4 -3 -2 11  2 -3 -4 -3 -2 -4 
Y -2 -2 -2 -3 -2 -1 -2 -3  2 -1 -1 -2 -1  3 -3 -2 -2  2  7 -1 -3 -2 -1 -4 
V  0 -3 -3 -3 -1 -2 -2 -3 -3  3  1 -2  1 -1 -2 -2  0 -3 -1  4 -3 -2 -1 -4 
B -2 -1  3  4 -3  0  1 -1  0 -3 -4  0 -3 -3 -2  0 -1 -4 -3 -3  4  0 -1 -4 
Z -1  0  0  1 -3  3  4 -2  0 -3 -3  1 -1 -3 -1  0 -1 -3 -2 -2  0  4 -1 -4 
X  0 -1 -1 -1 -2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2  0  0 -2 -1 -1 -1 -1 -1 -4')
{ @_ = split; $_ = shift @_; @{$b{$_}}{@r} = @_ }; #magic ^___^
$g = 4; $l = `tput cols`; #you have unix of course, right?
if (!defined $l) {$l = 80}; #these are the defaults: gap score and output line length
@s1 = split //, shift; unshift @s1, undef;
@s2 = split //, shift; unshift @s2, undef; #not very pretty, but well...
$w[0][0] = 0; $q[0][0] = 0; #here the dynamic algorithm begins
for (1..$#s1) { $w[$_][0] = -$_*$g; $q[$_][0] = 2 }
for (1..$#s2) { $w[0][$_] = -$_*$g; $q[0][$_] = 1 }
for $i (1..$#s1) { for $j (1..$#s2) { #this is quite dirty, will clean later
	$t1 = $w[$i][$j-1]-$g; $t2 = $w[$i-1][$j]-$g; 
	$w[$i][$j] = $w[$i-1][$j-1] + $b{$s1[$i]}{$s2[$j]}; $q[$i][$j] = -1;
	if ($t1>$w[$i][$j]) {$w[$i][$j] = $t1; $q[$i][$j] = 1};
	if ($t2>$w[$i][$j]) {$w[$i][$j] = $t2; $q[$i][$j] = 2};  
}}
print "Alignment score: $w[$#s1][$#s2]\nOptimal alignment is as follows:";
$i = $#s1; $j = $#s2; #this sucks, i know
while ($q[$i][$j]) { #actually this entire part is a bit creepy, will clean later too
	unshift @a1, $q[$i][$j]==1 ? "-" : $s1[$i];
	unshift @a2, $q[$i][$j]==2 ? "-" : $s2[$j];
	unshift @a3, ($a1[0] eq $a2[0]) & ($a1[0] ne "-") ? $a1[0] : $b{$a1[0]}{$a2[0]}>0 ? "+" : " ";
	if ($q[$i][$j]==1) {$j--} elsif ($q[$i][$j]==2) {$i--} else {$i--; $j--} #what a shame... i know...
}
while (@a1) {
	$s1=''; $s2=''; $s3='';
	for (1..$l) {
		if (@a1) { $s1 .= shift @a1; $s2 .= shift @a2; $s3 .= shift @a3 } else {break};
	}
	if ($s1) { print "\n$s1\n$s3\n$s2\n" }
}
