alignment.js

var calcAlignment = function(str1, str2) {
  // DPにより最短経路を計算
  var table = []
  var n = str1.length;
  var m = str2.length;
  for (var i = 0; i <= n; ++i) {
    table[i] = [];
    for (var j = 0; j <= m; ++j) {
      if (i === 0) { table[i][j] = { cost: -j, x: j - 1, y: 0 } }
      else if (j === 0) { table[i][j] = { cost: -i, x: 0, y: i - 1 } }
      else {
        var costs = [
          { x: j, y: i - 1, cost: table[i - 1][j].cost - 1 },
          { x: j - 1, y: i, cost: table[i][j - 1].cost - 1 },
          { x: j - 1, y: i - 1, cost: table[i - 1][j - 1].cost + (str1[i - 1] === str2[j - 1] ? 1 : -1) }
        ]
        var maxCost = Math.max.apply(null, costs.map(function(c) { return c.cost }))
        var back = costs.find(function(c) { return c.cost === maxCost })
        table[i][j] = {
          cost: maxCost,
          x: back.x,
          y: back.y
        }
      }
    }
  }
  
  // back trace
  var alignedStr1 = alignedStr2 = ''
  var x = m, y = n
  while (x > 0 && y > 0) {
    var nextX = table[y][x].x, nextY = table[y][x].y
    alignedStr2 = (nextX === x ? '-' : str2[x - 1]) + alignedStr2
    alignedStr1 = (nextY === y ? '-' : str1[y - 1]) + alignedStr1
    x = nextX
    y = nextY
  }
  return { cost: table[n][m].cost, str1: alignedStr1, str2: alignedStr2 }
}

calcAlignment('ACGT', 'ATCCT') // => {cost: 1, str1: "A-CGT", str2: "ATCCT"}