See the Wikipedia page on the Needleman-Wunsch algorithm.

Example

Setup:

import org.jblas.DoubleMatrix
import cats.implicits._
import axle.bio._
import NeedlemanWunsch.alignmentScore
import NeedlemanWunsch.optimalAlignment
import NeedlemanWunschDefaults._

implicit val laJblasDouble = {
  import spire.implicits.DoubleAlgebra
  axle.jblas.linearAlgebraDoubleMatrix[Double]
}

val dna1 = "ATGCGGCC"
val dna2 = "ATCGCCGG"

DNA Sequence Alignment

val nwAlignment =
  optimalAlignment[IndexedSeq[Char], Char, DoubleMatrix, Int, Double](
    dna1, dna2, similarity, gap, gapPenalty)
// nwAlignment: (IndexedSeq[Char], IndexedSeq[Char]) = (Vector(A, T, G, C, G, G, C, C, -, -),Vector(A, T, -, C, -, G, C, C, G, G))

Score aligment

import NeedlemanWunsch.alignmentScore
// import NeedlemanWunsch.alignmentScore

alignmentScore(nwAlignment._1, nwAlignment._2, gap, similarity, gapPenalty)
// res2: Double = 32.0

Compute distance

val space = NeedlemanWunschMetricSpace[IndexedSeq[Char], Char, DoubleMatrix, Int, Double](similarity, gapPenalty)
// space: axle.bio.NeedlemanWunschMetricSpace[IndexedSeq[Char],Char,org.jblas.DoubleMatrix,Int,Double] = NeedlemanWunschMetricSpace(<function2>,-5.0)

space.distance(dna1, dna2)
// res3: Double = 32.0