Needleman-Wunsch


use strict;
#debug = 1 displays score and traceback matrix
my $debug = 0;
my $now = time;

my $seq1="CCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATC";
my $seq2="CAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCAGTCGACTCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATCCCGATCGATGCATC";
# usage statement
#die "usage: $0 <sequence 1> <sequence 2>\n" unless @ARGV == 2;
# get sequences from command line
#my ($seq1, $seq2) = @ARGV;
#
#The Score Matrix
#
#    Seq1(j)      1       2       3       4 5 6 7 8 9 10
#Seq2  * C K H V F C R V C I
#(i) * 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10
#1 C -1 1 0 -1 -2 -3 -4 -5 -6 -7 -8
#2 K -2 0 2 1 0 -1 -2 -3 -4 -5 -6
#3 K -3 -1 1 1 0 -1 -2 -3 -4 -5 -6
#4 C -4 -2 0 0 0 -1 0 -1 -2 -3 -4
#5 F -5 -3 -1 -1 -1 1 0 -1 -2 -3 -4
#6 C -6 -4 -2 -2 -2 0 2 1 0 -1 -2
#7 K -7 -5 -3 -3 -3 -1 1 1 0 -1 -2
#8 C -8 -6 -4 -4 -4 -2 0 0 0 1 0
#9 V -9 -7 -5 -5 -3 -3 -1 -1 1 0 0

# scoring scheme
my $MATCH    =  1; # +1 for letters that match
my $MISMATCH = -1; # -1 for letters that mismatch
my $GAP      = -1; # -1 for any gap

# initialization
my @matrix;
$matrix[0][0]{score}   = 0;
$matrix[0][0]{pointer} = "none";
for(my $j = 1; $j <= length($seq1); $j++) {
$matrix[0][$j]{score}   = $GAP * $j;
$matrix[0][$j]{pointer} = "left";
}
for (my $i = 1; $i <= length($seq2); $i++) {
$matrix[$i][0]{score}   = $GAP * $i;
$matrix[$i][0]{pointer} = "up";
}

# fill
for(my $i = 1; $i <= length($seq2); $i++) {
for(my $j = 1; $j <= length($seq1); $j++) {
my ($diagonal_score, $left_score, $up_score);

# calculate match score
my $letter1 = substr($seq1, $j-1, 1);
my $letter2 = substr($seq2, $i-1, 1);
if ($letter1 eq $letter2) {
$diagonal_score = $matrix[$i-1][$j-1]{score} + $MATCH;
}
else {
$diagonal_score = $matrix[$i-1][$j-1]{score} + $MISMATCH;
}

# calculate gap scores
$up_score   = $matrix[$i-1][$j]{score} + $GAP;
$left_score = $matrix[$i][$j-1]{score} + $GAP;

# choose best score
if ($diagonal_score >= $up_score) {
if ($diagonal_score >= $left_score) {
$matrix[$i][$j]{score}   = $diagonal_score;
$matrix[$i][$j]{pointer} = "diagonal";
}
else {
$matrix[$i][$j]{score}   = $left_score;
$matrix[$i][$j]{pointer} = "left";
}
} else {
if ($up_score >= $left_score) {
$matrix[$i][$j]{score}   = $up_score;
$matrix[$i][$j]{pointer} = "up";
}
else {
$matrix[$i][$j]{score}   = $left_score;
$matrix[$i][$j]{pointer} = "left";
}
}
}
}

#print matrix

my $j = length($seq1);
my $i = length($seq2);
my @seq1 = ("*");
my @seq2 = ("*");
my @s1=split(//,$seq1);
my @s2=split(//,$seq2);
push (@seq1,@s1);
push (@seq2,@s2);
if ($debug ==1 ) {
print "The Score Matrix\n";
print "-----------------------\n";
print "\t";
foreach (@seq1) {
print $_."\t";
}
print "\n";
for (my $u=0;$u<=$i;$u++) {
print $seq2[$u]."\t";
for (my $v=0;$v<=$j;$v++) {
print $matrix[$u][$v]{score}."\t";
}
print "\n";
}

print "The Trace Matrix\n";
print "-----------------------\n";
print "\t";
foreach (@seq1) {
print $_."\t";
}
print "\n";
for (my $u=0;$u<=$i;$u++) {
print $seq2[$u]."\t";
for (my $v=0;$v<=$j;$v++) {

if ($matrix[$u][$v]{pointer} eq "none") {print  "N\t";}
if ($matrix[$u][$v]{pointer} eq "left") {print  "L\t";}
if ($matrix[$u][$v]{pointer} eq "up") {print  "U\t";}
if ($matrix[$u][$v]{pointer} eq "diagonal") {print  "D\t";}

}
print "\n";
}

}
my $align1 = "";
my $align2 = "";

my $score = $matrix[$i][$j]{score};

while (1) {
last if $matrix[$i][$j]{pointer} eq "none";

if ($matrix[$i][$j]{pointer} eq "diagonal") {
$align1 .= substr($seq1, $j-1, 1);
$align2 .= substr($seq2, $i-1, 1);
$i--; $j--;
}
elsif ($matrix[$i][$j]{pointer} eq "left") {
$align1 .= substr($seq1, $j-1, 1);
$align2 .= "-";
$j--;
}
elsif ($matrix[$i][$j]{pointer} eq "up") {
$align1 .= "-";
$align2 .= substr($seq2, $i-1, 1);
$i--;
}
}

$align1 = reverse $align1;
$align2 = reverse $align2;

print "Best Alignment\n";
print "--------------\n";
print "Seq1:\t$align1\n";
print "Seq2:\t$align2\n";
print "score = $score\n";

print "size:".length($seq1)+length($seq2)." letters => ";
print time - $now." second\(s\)\n";