# Smith-Waterman-Gotoh Algorithm - how to determine an overall similarity percentage

Using the Smith-Waterman-Gotoh algorithm I want to get an overall similarity percentage between two sequences. What would be the best way to do this?

eg. comparing strings COELACANTH and PELICAN in this example gives a score of 4 with alignment:

ELACAN
ELICAN


How would I then go an determine the overall similarity percentage between COELACANTH and PELICAN based on this?

I don't know how to write math algebra like on the Wikipedia page for Smith-Waterman, so i'll use pseudo code. I found the logic at SimMetrics in the SmithWatermanGotoh java code.

str1 = PELICAN
str2 = COELACANTH
matchValue = 1 #in the comparisons below, when characters are equal, assign this value
mismatchValue = -2 #in the comparisons below, when characters are not equal, assign this value
gapValue = -0.5 #the gap penalty used in smith-waterman

# get the maxDistance which is the smallest number of characters between str1 and str2 multiplied by
# the largest of matchValue and gapValue
maxDistance = min(length(str1), length(str2)) x max(matchValue, gapValue);

# function to compare character at index aIndex of string a with character at index bIndex of string b
function compareCharacters(a, aIndex, b, bIndex, matchValue, mismatchValue) {
if a[aIndex] === b[bIndex]
return matchValue
else
return mismatchValue
}

v0 = an array
v1 = an array

lengthOfStr1 = number of characters in str1
lengthOfStr2 = number of characters in str2

# do the smith waterman similarity measure (currentMax)
currentMax = v0[0] = max(0, gapValue, compareCharacters(str1, 0, str2, 0, matchValue, mismatchValue))

for (j = 1; j < lengthOfStr2; j++) {
v0[j] = max(0, v0[j - 1] + gapValue,
compareCharacters(str1, 0, str2, j, matchValue, mismatchValue))

currentMax = max(currentMax, v0[j])
}

for (i = 1; i < lengthOfStr1; i++) {
v1[0] = max(0, v0[0] + gapValue, compareCharacters(str1, i, str2, 0, matchValue, mismatchValue))

currentMax = max(currentMax, v1[0])

for (j = 1; j < lengthOfStr2; j++) {
v1[j] = max(0, v0[j] + gapValue, v1[j - 1] + gapValue,
v0[j - 1] + compareCharacters(str1, i, str2, j, matchValue, mismatchValue))

currentMax = max(currentMax, v1[j])
}

for (j = 0; j < lengthOfStr2; j++) {
v0[j] = v1[j]
}
}

# calculate the overallSimilarity between the strings
overallSimilarity = currentMax / maxDistance #<- 0.4767 for COELACANTH vs PELICAN