#################################################################################################
#This is to align two sequences with the Needleman-Wunsch algorithm;
#The input is two string, the delimeter for seperating the string into elements, the score for
# the mismatch of the element, and the score for the gap
#The output is the global alignment of two strings
#################################################################################################
sub globalAlignment{
	my($string1,$string2,$delimeter,$mismatchScore,$gapScore)=@_;
	my @sa1=split/$delimeter/,$string1;
	my @sa2=split/$delimeter/,$string2;

	my ($len_s1, $len_s2) = (0,0); # length of s1/s2

	my %table;	    # Dynamic Programming Table 
	$table{0}{0}=0;
	my $max_len = scalar(@sa1) > scalar(@sa2) ? scalar(@sa1): scalar(@sa2); # for global
	while ($len_s1 <= (scalar @sa1)) {
		while ($len_s2 <= scalar @sa2) {
			my ($candidate1, $candidate2, $candidate3) = ($max_len,$max_len,$max_len);
			if ($len_s1 > 0 and $len_s2 > 0) {
				$candidate1 = int($table{$len_s1-1}{$len_s2-1})+ ( ( $sa1[$len_s1-1] eq $sa2[$len_s2-1] )? 0 : $mismatchScore );
			}
			if ($len_s1 > 0) {
				$candidate2 = int($table{$len_s1-1}{$len_s2}) + $gapScore;   #处理横向和纵向的增加gap时引入的分
			}
			if ($len_s2 > 0) {
				$candidate3 = int($table{$len_s1}{$len_s2 - 1})  + $gapScore;
			}
			if ($len_s1 > 0 or $len_s2 > 0){
				$table{$len_s1}{$len_s2} = min ( $candidate1, $candidate2, $candidate3) ;
			}
			$len_s2 +=1;
		}
		$len_s2 = 0;
		$len_s1 +=1;
	}

	my ($i, $j) = (0, 0);
	my (@as1, @as2);
	my $baseline = 0;
	$i = scalar @sa1;
	$j = scalar @sa2;
	while ( $i >0 && $j >0) {
		$baseline = min($table{$i-1}{$j-1},$table{$i-1}{$j},$table{$i}{$j-1});
		if ($table{$i-1}{$j-1} == $baseline) {
			push @as1, $sa1[$i-1];
			push @as2, $sa2[$j-1];
			$i--;
			$j--;
		}elsif ($table{$i}{$j-1} == $baseline) {
			push @as1, "-"; # gap
			push @as2, $sa2[$j-1];
			$j--;
		}elsif ($table{$i-1}{$j} == $baseline) {
			push @as1, $sa1[$i-1];
			push @as2, "-"; # gap
			$i--;
		}else {
			die "$!";
		}
	}
	#The following "while" is to make the alignment complete.
	while($i>0){
		push(@as1,$sa1[$i-1]);
		push(@as2,"-");
		$i--;
	}
	while($j>0){
		push(@as1,"-");
		push(@as2,$sa2[$j-1]);
		$j--;
	}

	@as1=reverse @as1;
	@as2=reverse @as2;

	return(join($delimeter,@as1),join($delimeter,@as2));
}


########################################################################################
sub min{
          my(@array)=@_;
         @array=sort {$a<=>$b} @array;
         return $array[0];
}


#######################################################################################
sub max{
        my(@array)=@_;
        @array=sort {$a<=>$b}@array;
        return $array[-1];
}