Instantly share code, notes, and snippets.

# dkohlsdorf/Alignment.scala Last active May 26, 2017

General Sequence Alignment
 class Alignment[A]( init: (Int, Int) => Double, rank: (Double, Double, Double, A, A) => Double ) { def score(x: Array[A], y: Array[A]): Double = { val n = x.size val m = y.size val dp = Array.ofDim[Double](n + 1, m + 1) for(i <- 0 until n + 1) dp(i)(0) = init(i, 0) for(j <- 0 until m + 1) dp(0)(j) = init(0, j) for(i <- 1 until n + 1) { for(j <- 1 until m + 1) { dp(i)(j) = rank( dp(i - 1)(j), // insertion dp(i - 1)(j - 1), // match dp(i)(j - 1), // deletion x(i - 1), // current sample in x y(j - 1) // current sample in y ) } } dp(n)(m) } } object Aligner { class DTW extends Alignment[Double]( init = (i: Int, j: Int) => if(i == 0 && j == 0) 0.0 else Double.PositiveInfinity, rank = (insert: Double, matching: Double, delete: Double, x: Double, y: Double) => if(insert < matching && insert < delete) insert + math.pow(x - y, 2) else if (delete < insert && delete < matching) delete + math.pow(x - y, 2) else matching + math.pow(x - y, 2) ) class Levensthein extends Alignment[Char]( init = (i: Int, j: Int) => if(i == 0 && j == 0) 0.0 else if(i == 0) j else i, rank = (insert: Double, matching: Double, delete: Double, x: Char, y: Char) => if(insert < matching && insert < delete) insert + 1 else if (delete < insert && delete < matching) delete + 1 else matching + (if(x == y) 0.0 else 1.0) ) final val Sim = Map( ('a', 'a') -> 10, ('a', 'g') -> -1, ('g', 'a') -> -1, ('a', 'c') -> -3, ('c', 'a') -> -3, ('a', 't') -> -4, ('t', 'a') -> -4, ('g', 'g') -> 7, ('g', 'c') -> -5, ('c', 'g') -> -5, ('g', 't') -> -3, ('t', 'g') -> -3, ('c', 'c') -> 9, ('c', 't') -> 0, ('t', 'c') -> 0, ('t', 't') -> 8 ) final val Gap = -5 class NeedlemanWunsch extends Alignment[Char]( init = (i: Int, j: Int) => if(i == 0 && j == 0) 0.0 else if(i == 0) j * Gap else i * Gap, rank = (insert: Double, matching: Double, delete: Double, x: Char, y: Char) => if(insert > matching && insert > delete) insert + Gap else if (delete > insert && delete > matching) delete + Gap else matching + Sim(x, y) ) def main(args: Array[String]): Unit = { println("Different Alignemnts") val x = Array(1.0, 2.0, 1.0, 2.0) val y = Array(1.0, 1.0, 2.0) val dtw = new DTW println(s"DTW mindist = \${dtw.score(x, y)}") val xs = "hallo".toArray val ys = "halo".toArray val leven = new Levensthein println(s"Levensthein mindist = \${leven.score(xs, ys)}") val xbio = "AGACTAGTTAC".toLowerCase.toArray val ybio = "CGAGACGT".toLowerCase.toArray val nw = new NeedlemanWunsch println(s"Needleman - Wunsch max score \${nw.score(xbio, ybio)}") } }