Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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)}")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment