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

Question

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?

Answer 1

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