Wagner-Fischer Demo

Demonstration of the Wagner-Fischer Algorithm for sequence alignment and the calculation of the edit distance.

by LinguList

HTML

<h2>Wagner-Fischer Demo</h2>
<input type="text" style="width:500px" id="seqA" /> 
<br/>
<input type="text" style="width:500px" id="seqB" />
<button onclick="startDemo();">GO!</button>
<button onclick="stopDemo();">STOP!</button>
<button onclick="resumeDemo();">RESUME!</button>
<input id="speed" type="range" min="0" max="3000" value="250" />
<br/>
<div id="answer">
<div id="nw"></div>
<div id="number"></div>
<div id="alignment"></div>
</div>
<div id="counter" style="display:none">0</div>

CSS

.alm {
  border: 2px solid gray;
}
.alm td {
  width: 40px;
  height: 40px;
  text-align: center;
  border: 3px solid lightgray;
  
}

.alms {
	display: table-cell;
	width: 40px;
	height: 40px;
	text-align:center;
	border: 3px solid lightgray;
	padding: 5px;
	vertical-align: center;
	font-weight: bold;
	background: black;
	color: white;
}

.tb0 {
	border-left: 3px solid DarkGreen!important;
	border-top: 3px solid DarkGreen!important;
}

.tb1 {
	border-top: 3px solid Blue!important;
}

.tb2 {
	border-left: 3px solid Crimson!important;
}

.path {
	background-color: gray;
	font-weight: bold;
	color:white;
}

.popup {
	position: absolute;
	border: 3px solid Crimson;
	padding: 5px;
	font-weight: bold;
	font-size;
}

#answer div {
	float: left;
	display: table-cell;
	margin-right: 20px;
}

.cells {
	text-align: left;
}
.cells th,td {
	text-align: left;
	border: 3px solid lightgray;
}

JavaScript

function editList(seqA, seqB, debug)
{
  /* check whether debug variable is passed */
  if (typeof debug == 'undefined') {
    debug = false;
  }
  else {
    debug = true;
  }
  
  /* return nothing if either of the lists is empty */
  if(seqA.length == 0 || seqB.length == 0)
  {
    return;
  }
  
  /* get the lengths of the sequences */
  var alen = seqA.length;
  var blen = seqB.length;

  /* declare variables in local environment */
  var i, j; // numbers
  var gapA, gapB, dist; // floats
  var charA, charB; // characters
  var inline;

  /* create the matrix */
  var matrix = [];
  for(i=0;i<alen+1;i++) {
    inline = [];
    for(var j=0;j<blen+1;j++) {
      inline.push(0);
    }
    matrix.push(inline);
  }
  
  /* initialize matrix */
  for(i=1;i<blen+1;i++) {
    matrix[0][i] = i;
  }
  for(i=1;i<alen+1;i++) {
    matrix[i][0] = i;
  }
  
  /* create the traceback */
  var traceback = [];
  for(var i=0;i<alen+1;i++) {
    var inline = [];
    for(var j=0;j<blen+1;j++) {
      inline.push(0);
    }
    traceback.push(inline);
  }

  /* initialize traceback */
  for(i=1;i<blen+1;i++) {
    traceback[0][i] = 2;
  }
  for(i=1;i<alen+1;i++) {
    traceback[i][0] = 1;
  }

  /* start the iteration to fill the matrix */
  for(i=1;i<alen+1;i++) {
    for(j=1;j<blen+1;j++) {
      
      /* get the character in both sequences at their respective position */
      charA = seqA[i-1];
      charB = seqB[j-1];
      
      /* check the similarity between the characters to get the local distance */
      if(charA == charB) {
        dist = matrix[i-1][j-1];
      }
      else {
        dist = matrix[i-1][j-1]+1;
      }
      
      /* we have the distance for substitution, now we need the gaps */
      gapA = matrix[i-1][j]+1;
      gapB = matrix[i][j-1]+1;
    
      /* find the minimal value */
      if(dist < gapA && dist < gapB) {
        matrix[i][j] = dist;
      }
      else if(gapA < gapB) {
        matrix[i][j] = gapA ;
        traceback[i][j] = 1;
      }
...