nussinov.js

const nussinov = (sequence) => {
  const length = sequence.length
  const table =
    (new Array(length))
      .fill(0)
      .map((i) => (new Array(length)).fill({ value: Infinity, pairs: [] }))

  for (let i = 0; i < length; i++) {
    table[i][i] = { value: 0, pairs: [] }
    table[i][i + 1] = { value: 0, pairs: [] }
  }

  const cost = (i, j) => {
    const isPair =
      sequence[i] === 'A' && sequence[j] === 'U' ||
      sequence[i] === 'U' && sequence[j] === 'A' ||
      sequence[i] === 'G' && sequence[j] === 'C' ||
      sequence[i] === 'C' && sequence[j] === 'G'

    return isPair ? -1 : Infinity
  }

  for (let d = 2; d < length; d++) {
    for (let i = 0; i < length - d; i++) {
      const j = i + d
      const connect_ij = table[i + 1][j - 1].value + cost(i, j)
      const value =
        Math.min(table[i + 1][j].value, table[i][j - 1].value, connect_ij)
      const pairs =
        value === table[i + 1][j].value ? table[i + 1][j].pairs :
        value === table[i][j - 1].value ? table[i][j - 1].pairs :
        [...table[i + 1][j - 1].pairs, [i, j]]

      table[i][j] = { value, pairs }

      for (let k = i + 1; k < j - 1; k++) {
        const value =
          Math.min(table[i][j].value, table[i][k].value + table[k + 1][j].value)
        const pairs =
          value === table[i][j].value ? table[i][j].pairs :
          [...table[i][k].pairs, ...table[k + 1][j].pairs]
        table[i][j] = { value, pairs }
      }
    }
  }

  console.log(table[0][length - 1])
}

const sequence = 'UCGUUCGGUAACA'
nussinov(sequence)