Needleman–Wunsch Algorithm

NeedlemanWunschAlgorithm.js

// code written by skatpgusskat 남세현
// https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

const dnaSequence1 = 'GCTAGGACTG'.split('');
const dnaSequence2 = 'ACGGATGCAT'.split('');

const LEFT = 'LEFT';
const TOP = 'TOP';
const TOP_LEFT = 'TOP_LEFT';

const table = []; // table[x][y] = { value, arrows: [LEFT | TOP | TOP_LEFT], isAnswerNode: boolean }

const matchScore = 2;
const mismatchScore = -1;
const indel = -1;

function initalizeTable(table, mismatchScore, lengthX, lengthY) {
  for (let i = 0; i < lengthX + 1; i += 1) {
    table[i] = [];
    table[i][0] = {
      value: i * mismatchScore,
    };
  }
  for (let i = 0; i < lengthY + 1; i += 1) {
    table[0][i] = {
      value: i * mismatchScore,
    };
  }
}

function runNeedlemanWunsch(table, dnaSequenceX, dnaSequenceY, matchScore, mismatchScore, indel) {
  for (let x = 1; x < dnaSequenceX.length + 1; x += 1) {
    for (let y = 1; y < dnaSequenceY.length + 1; y += 1) {

      const matchingScore = dnaSequenceX[x - 1] === dnaSequenceY[y - 1]
        ? matchScore
        : mismatchScore;

      const left = table[x - 1][y].value + indel;
      const topLeft = table[x - 1][y - 1].value + matchingScore;
      const top = table[x][y - 1].value + indel;

      const maximum = Math.max(left, topLeft, top);

      const arrows = [];

      if (left === maximum) {
        arrows.push(LEFT);
      }
      if (topLeft === maximum) {
        arrows.push(TOP_LEFT);
      }
      if (top === maximum) {
        arrows.push(TOP);
      }

      table[x][y] = {
        value: maximum,
        arrows,
      };
    }
  }
}



// intermediateResult : { sequenceX: string, sequenceY: string, traces: [{ x: number, y: number}] }
function traceTable(table, x, y, dnaSequenceX, dnaSequenceY, intermediateResult = { sequenceX: '', sequenceY: '' }) {
  table[x][y].isAnswerNode = true;

  if (x === 0 || y === 0) {
    const answerX = `${dnaSequenceX.slice(0, x).join('')}${'_'.repeat(y)}${intermediateResult.sequenceX}`
    const answerY = `${dnaSequenceY.slice(0, y).join('')}${'_'.repeat(x)}${intermediateResult.sequenceY}`
    return [{
      sequenceX: answerX,
      sequenceY: answerY,
    }];
  }
  return table[x][y].arrows.map((arrow) => {
    switch (arrow) {
      case LEFT:
        return traceTable(table, x - 1, y, dnaSequenceX, dnaSequenceY, {
          sequenceX: `${dnaSequenceX[x - 1]}${intermediateResult.sequenceX}`,
          sequenceY: `_${intermediateResult.sequenceY}`,
        });
      case TOP_LEFT:
        return traceTable(table, x - 1, y - 1, dnaSequenceX, dnaSequenceY, {
          sequenceX: `${dnaSequenceX[x - 1]}${intermediateResult.sequenceX}`,
          sequenceY: `${dnaSequenceY[y - 1]}${intermediateResult.sequenceY}`,
        });
      case TOP:
        return traceTable(table, x, y - 1, dnaSequenceX, dnaSequenceY, {
          sequenceX: `_${intermediateResult.sequenceX}`,
          sequenceY: `${dnaSequenceY[y - 1]}${intermediateResult.sequenceY}`,
        });
    }
  })
    .reduce((acc, val) => acc.concat(val), []);
}

function drawAnswerTable(table, dnaSequenceX, dnaSequenceY) {
  const drawTable = [];
  for (let x = 0; x < 2 * dnaSequenceX.length + 2; x += 1) {
    drawTable.push([]);
    for (let y = 0; y < 2 * dnaSequenceY.length + 2; y += 1) {
      drawTable[x].push('');
    }
  }


  for (let i = 0; i < dnaSequenceX.length; i += 1) {
    drawTable[2 * i + 3][0] = dnaSequenceX[i];
  }
  for (let i = 0; i < dnaSequenceY.length; i += 1) {
    drawTable[0][2 * i + 3] = dnaSequenceY[i];
  }

  for (let x = 0; x < dnaSequenceX.length + 1; x += 1) {
    for (let y = 0; y < dnaSequenceY.length + 1; y += 1) {
      const { value, arrows, isAnswerNode } = table[x][y];
      const valuePositionX = 2 * x + 1;
      const valuePositionY = 2 * y + 1;
      drawTable[valuePositionX][valuePositionY] = value;
      if (!arrows) {
        continue;
      }
      if (arrows.includes(LEFT)) {
        drawTable[valuePositionX - 1][valuePositionY] = isAnswerNode ? '⇦' : '←';
      }
      if (arrows.includes(TOP_LEFT)) {
        drawTable[valuePositionX - 1][valuePositionY - 1] = isAnswerNode ? '⬁' : '↖';
      }
      if (arrows.includes(TOP)) {
        drawTable[valuePositionX][valuePositionY - 1] = isAnswerNode ? '⇧' : '↑';
      }
    }
  }
  return drawTable;
}

function zeroPad(value, base) {
  const len = (String(base).length - String(value).length) + 1;
  return len > 0 ? `${new Array(len).join(' ')}${value}` : value;
}

function printAnserTable(drawTable, dnaSequenceX, dnaSequenceY) {
  for (let y = 0; y < 2 * dnaSequenceY.length + 2; y += 1) {
    const row = [];
    for (let x = 0; x < 2 * dnaSequenceX.length + 2; x += 1) {
      const item = drawTable[x][y];
      const formatted = zeroPad(item, 100);
      row.push(formatted);
    }
    console.log(row.join(''));
  }
}

initalizeTable(table, mismatchScore, dnaSequence1.length, dnaSequence2.length);
runNeedlemanWunsch(table, dnaSequence1, dnaSequence2, matchScore, mismatchScore, indel);
const results = traceTable(table, dnaSequence1.length, dnaSequence2.length, dnaSequence1, dnaSequence2);
console.log(results);
const drawTable = drawAnswerTable(table, dnaSequence1, dnaSequence2);
printAnserTable(drawTable, dnaSequence1, dnaSequence2)