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";
You must be logged in to post a comment.