text:
<repo_name>maxkvant/BioAlgCourse<file_sep>/src/main/scala/Hmm/Aligner.scala
package Hmm

import Hmm.Aligner.Matrix
import Hmm.Main.printMatrix

object Aligner {
  val moves: Seq[(Int, Int)] = List((1, 1), (1, 0), (0, 1))
  type Matrix[T] = Array[Array[T]]
}

case class Aligner(markovModel: Matrix[Double], initProbability: Array[Double], mismatchGenP: Double, gapGenP: Double) {
  type Array3D[T] = Array[Array[Array[T]]]

  require(markovModel.length == 3)
  markovModel.foreach(row => require(row.length == 3))

  import Aligner._

  def cost(i: Int, j: Int)(moveI1: Int)(moveI2: Int)(implicit strings: (String, String)): Double = {
    val (s, t) = strings
    val (di, dj) = moves(moveI2)
    val genCost = (s.lift(i - 1), t.lift(j - 1), moveI2) match {
      case (_, _, 1) => gapGenP
      case (_, _, 2) => gapGenP
      case (Some(c1), Some(c2), 0) => if (c1 == c2) 1.0 else mismatchGenP
      case _ => 1.0
    }
    markovModel(moveI1)(moveI2) * genCost
  }

  def Viterbi(str1: String, str2: String): (String, String) = {
    implicit val strings: (String, String) = (str1, str2)
    val n = str1.length
    val m = str2.length

    val dp: Array3D[Double] = Array.fill(n + 1, m + 1, 3)(0.0)
    dp(0)(0) = initProbability.clone
    val prev1: Array3D[List[Char]] = Array.fill(n + 1, m + 1, 3)(Nil)
    val prev2: Array3D[List[Char]] = Array.fill(n + 1, m + 1, 3)(Nil)

    for (i2 <- 0 to n; j2 <- 0 to m; if (i2, j2) != (0, 0)) {
      for (moveI2 <- moves.indices) {
        val (dpMax, i1, j1, moveI1) =
          (for {
            moveI1 <- moves.indices
            (di, dj) = moves(moveI2)
            (i1, j1) = (i2 - di, j2 - dj)
            dpValue: Double = if (i1 >= 0 && j1 >= 0) dp(i1)(j1)(moveI1) else 0
          } yield (cost(i2, j2)(moveI1)(moveI2) * dpValue, i1, j1, moveI1))
            .max

        if (i1 >= 0 && j1 >= 0) {
          dp(i2)(j2)(moveI2) = dpMax
          prev1(i2)(j2)(moveI2) = (if (moves(moveI2)._1 == 1) str1(i2 - 1) else '-') :: prev1(i1)(j1)(moveI1)
          prev2(i2)(j2)(moveI2) = (if (moves(moveI2)._2 == 1) str2(j2 - 1) else '-') :: prev2(i1)(j1)(moveI1)
        }
      }
    }
    val (dpMax, maxI) = (for (i <- dp(n)(m).indices) yield (dp(n)(m)(i), i)).max
    (prev1(n)(m)(maxI).reverse.mkString, prev2(n)(m)(maxI).reverse.mkString)
  }

  def FB(str1: String, str2: String): Matrix[Double] = {
    implicit val strings: (String, String) = (str1, str2)
    val n = str1.length
    val m = str2.length

    val dpBefore: Array3D[Double] = Array.fill(n + 1, m + 1, 3)(0.0)
    dpBefore(0)(0) = initProbability.clone

    for (i2 <- 0 to n;
         j2 <- 0 to m
         if (i2, j2) != (0, 0);
         moveI2 <- moves.indices) {
          dpBefore(i2)(j2)(moveI2) = (for {
              moveI1 <- moves.indices
              (di, dj) = moves(moveI2)
              (i1, j1) = (i2 - di, j2 - dj)
              if i1 >= 0 && j1 >= 0
            } yield dpBefore(i1)(j1)(moveI1) * cost(i2, j2)(moveI1)(moveI2))
              .sum
    }

    val dpAfter: Array3D[Double] = Array.fill(n + 1, m + 1, 3)(0.0)
    dpAfter(n)(m) = Array(1.0, 1.0, 1.0)

    for (i1 <- n to 0 by -1;
         j1 <- m to 0 by -1
         if (i1, j1) != (n, m);
         moveI1 <- moves.indices) {
          dpAfter(i1)(j1)(moveI1) = (for {
              moveI2 <- moves.indices
              (di, dj) = moves(moveI2)
              (i2, j2) = (i1 + di, j1 + dj)
              if i2 <= n && j2 <= m
            } yield cost(i2, j2)(moveI1)(moveI2) * dpAfter(i2)(j2)(moveI2))
              .sum
    }

    val dp = Array.fill(n + 1, m + 1, 3)(0.0)

    for (i <- 0 to n; j <- 0 to m) {
      dp(i)(j) = (dpAfter(i)(j) zip dpBefore(i)(j)).map({case (a, b) => a * b})
    }

    val norm1 = dp(n)(m).sum

    val res = dp.map(_.map(_.apply(0) / norm1))
    res
  }

  def BacktrackFB(s: String, t: String): Matrix[Double] = {
    implicit val strings: (String, String) = (s, t)
    println("backtrackFB")

    val n = s.length
    val m = t.length
    val ans: Matrix[Double] = Array.fill(n, m)(0.0)
    var sum: Double = 0
    def dfs(i: Int, j: Int, moveI1: Int, p: Double, matches: List[(Int,Int)]): Unit = {
      if (i == n && j == m) {
        sum += p
        for ((i, j) <- matches) {
          ans(i)(j) += p
        }
      }
      for (((di, dj), moveI2) <- moves.zipWithIndex if i + di <= n && j + dj <= m) {
        val matches2 = if (moveI2 == 0) (i, j) :: matches else matches
        dfs(i + di, j + dj, moveI2, p * cost(i + di, j + dj)(moveI1)(moveI2), matches2)
      }
    }
    for (i <- moves.indices) {
      dfs(0, 0, i, initProbability(i), Nil)
    }
    val res = ans.map(_.map(_ / sum))
    printMatrix(res)
    res
  }
}<file_sep>/src/main/scala/Rna/Main.scala
package Rna

object Main {
  def main(args: Array[String]): Unit = {
    def run(t: String) = {
      val res = Nussinov(t)
      println (res.length)
      res.foreach ( {case (i, j) => println (s"${t (i)} ${i + 1} ${j + 1} ${t (j)}")})
    }

    val s = "AAAAAAAAAAAAAAAAAAAAAAAAAGGGGGGGGGGGGGGGGGGGGGGGGCCCCCCCCCCCCCCCCCCCUUUUUUUUUUUUUUUUUUUUUUUUUUU"
    val t = "AAACAUGAGGAUUACC"

    run(t)
  }
}
<file_sep>/readme.md
### hw02

#### example
`sbt run`

`ATGC`

`ATGT`

###### output

`ATGC-`

`ATG-T`<file_sep>/build.sbt
name := "BioAlgCourse"

version := "0.1"

scalaVersion := "2.12.3"

libraryDependencies += "guru.nidi" % "graphviz-java" % "0.2.2"
libraryDependencies += "ch.qos.logback" % "logback-classic" % "1.2.3"
libraryDependencies += "ch.qos.logback" % "logback-classic" % "1.2.3" % "test"<file_sep>/src/main/scala/DebrujinGraph/DebrujinGraph.scala
package DebrujinGraph

import java.io.File

import guru.nidi.graphviz.engine.{Format, Graphviz}
import guru.nidi.graphviz.model.Factory._
import guru.nidi.graphviz.parse.Parser

import scala.collection.mutable.ArrayBuffer

class DebrujinGraph(n1: Int) {

  import DebrujinGraph._
  val n: Int = n1 - 1
  val vertices: List[V] = (0 until (1 << n)).toList
  val edges: List[List[V]] = vertices.map(v => List(v >> 1, (v >> 1) + (1 << (n - 1))))
  val cycle: List[V] = {
    val degUsed: Array[V] = Array.fill[V](vertices.size)(0)
    val cycle = ArrayBuffer[V]()
    def dfs(v: V): Unit = {
      while (degUsed(v) < edges(v).size) {
        degUsed(v) += 1
        dfs(edges(v)(degUsed(v) - 1))
      }
      cycle.append(v)
    }
    dfs(vertices.head)
    val res = cycle.reverse.toList
    for ((a, b) <- res zip res.tail) {
      require(edges(a).contains(b))
    }
    res
  }

  val str: String = cycle.take(cycle.size - 1).map(_ & 1).map(_.toString).mkString

  require({
    val str2 = str + str
    for {
      i <- 0 until str.length
    } yield str2.substring(i, i + n1 + 1)
  }.toSet.size == (1 << n1))

  def saveDot(): Unit = {
    val cycleStr = cycle.map(VString)
    val nodes = vertices.map(VString).map(v => v -> mutNode(v)).toMap

    val dotStr = s"digraph Debrujin_$n1 {\n" +
      (cycleStr zip cycleStr.tail).zipWithIndex.map({ case ((v, u), i) =>
        s"$v -> $u [label = $i]"
      })
        .mkString("\n") +
      "\n}"

    val gr = Parser.read(dotStr)
    println(gr)
    val outfile = new File("png/out.png")
    println(Format.PNG)
    println(outfile)
    Graphviz.fromGraph(gr).render(Format.PNG).toFile(outfile)
  }

  def VString(v: V): String = {
    val s = v.toBinaryString.reverse
    s + "0" * (n - s.length)
  }
}

object DebrujinGraph {
  type V = Int
}
<file_sep>/src/main/scala/Trees/Main.scala
package Trees

import Trees.TreeBuilder._

import scala.io.StdIn._

object Main {
  val treeBuilder: TreeBuilder = NJ

  def main(args: Array[String]): Unit = {
    test2()
  }

  def consoleTask(): Unit = {
    val n = readInt()
    val labels: Array[String] = readLine().split(" ")
    val read_dist: Matrix =
      for (i <- (0 until n).toArray) yield readLine().split(" ").map(_.toDouble)

    val dist = toMatrix(read_dist)

    val tree = treeBuilder.build(dist, labels)
    println(tree.newick)
  }

  def test() {
    val d: Matrix = toMatrix(Array(
      Array(0),
      Array(16, 0),
      Array(16, 8, 0),
      Array(10, 8, 4, 0)
    ))
    val labels = Array("a", "b", "c", "d")
    println(WPGMA.build(d, labels).newick)
    println(UPGMA.build(d, labels).newick)
    println(NJ.build(d, labels).newick)
  }

  def test2() {
    val labels = Array("a", "b", "c", "d", "e", "f")
    val d: Matrix = toMatrix(Array(
      Array(0),
      Array(5, 0),
      Array(4, 7, 0),
      Array(7, 10, 7, 0),
      Array(6, 9, 6, 5, 0),
      Array(8, 11, 8, 9, 8, 0)
    ))

    println(WPGMA.build(d, labels).newick)
    println(UPGMA.build(d, labels).newick)
    println(NJ.build(d, labels).newick)
  }

}
<file_sep>/src/main/scala/Trees/TreeBuilder.scala
package Trees

import Trees.TreeBuilder.Matrix

trait TreeBuilder {
  def build(dist: Matrix, labels: Array[String]): Tree

  protected def checkSizes(dist: Array[Array[Double]], labels: Array[String]): Unit = {
    require(labels.length > 0)
    require(labels.length == dist.length)
    dist.foreach(subdist => require(subdist.length == dist.length))
    for (i <- labels.indices; j <- labels.indices; if i <= j) {
      require(dist(i)(j) == dist(i)(j))
      require(dist(i)(i) == 0)
    }
  }
}

object TreeBuilder {
  type Matrix = Array[Array[Double]]

  // 0         0 a b
  // a 0   =>  a 0 c ...
  // b c 0     b c 0
  //  ...       ...

  def toMatrix(d: Array[Array[Double]]): Matrix = {
    for {
      i <- d.indices.toArray
      res = for {
        j <- d.indices.toArray
        dij = if (i >= j) d(i)(j) else d(j)(i)
      } yield dij
    } yield res
  }
}<file_sep>/src/main/scala/Rna/Nussinov.scala
package Rna

object Nussinov {
  def complement(a: Char, b: Char): Boolean = Set(
    ('A', 'U'),
    ('U', 'A'),
    ('G', 'C'),
    ('C', 'G')
  ).apply(a, b)

  def apply(s: String): List[(Int, Int)] = {
    val n = s.length
    val dp = Array.fill[Double](n+1, n)(0.0)
    val prev = Array.fill[List[(Int, Int)]](n, n)(Nil)

    for (len <- 4 to n; l <- 0 to (n - len); r = l + len - 1) {
      val (dp1, lAns, rAns) = (for  {
        k <- l until r
        dp_sum = dp(l)(k) + dp(k+1)(r)
      } yield (dp_sum, prev(l)(k), prev(k+1)(r))).maxBy(_._1)

      dp(l)(r) = dp1
      prev(l)(r) = lAns ++ rAns

      if (complement(s(l), s(r)) && dp1 < dp(l + 1)(r - 1) + 1) {
        dp(l)(r) = dp(l + 1)(r - 1) + 1
        prev(l)(r) = (l, r) :: prev(l + 1)(r - 1)
      }
    }
    prev(0)(n-1)
  }
}
<file_sep>/src/main/scala/Trees/NJ.scala
package Trees

import Trees.TreeBuilder.Matrix

import scala.collection.mutable
import scala.util.Random

object NJ extends TreeBuilder {
  override def build(dist: Matrix, labels: Array[String]): Tree = {
    checkSizes(dist, labels)

    val d: Matrix = dist.map(_.clone)
    val roots: mutable.Buffer[Int] = labels.indices.toBuffer[Int]
    val trees: Array[RootedTree] = labels.map(name => RootedTree(Seq(), name))

    while (roots.length > 2) {
      val n = roots.length
      val distSum: Array[Double] = labels.indices.map(i => (for (j <- roots) yield d(i)(j)).sum).toArray

      val (minD, mI, mJ, i, j) = (for {
        i <- roots
        j <- roots
        if i < j
        mI = distSum(i) / (n - 2)
        mJ = distSum(j) / (n - 2)
      } yield (d(i)(j) - mI - mJ, mI, mJ, i, j)).min

      val v: Int = i
      roots -= i
      roots -= j

      for (t <- roots) {
        val newD = 0.5 * (d(i)(t) + d(t)(j) - d(i)(j))
        d(t)(v) = newD
        d(v)(t) = newD
      }

      trees(v) = RootedTree(Seq(Edge(trees(i), 0.5 * minD + mI), Edge(trees(j), 0.5 * minD + mJ)), "")
      roots += v
    }

    if (roots.length == 1) {
      trees(roots.head)
    } else {
      val finalD: Double = d(roots(0))(roots(1))
      val trees2 = Random.shuffle(roots.map(trees))
      val rootSeq: Seq[Edge] = trees2(0).seq :+ Edge(trees2(1), finalD)
      RootedTree(rootSeq, trees2(0).name)
    }
  }
}
<file_sep>/src/main/scala/Alignment/Main.scala
package Alignment

import scala.io.StdIn

object Main {
  def main(args: Array[String]): Unit = {
    val str1 = StdIn.readLine()
    val str2 = StdIn.readLine()
    val (s1, s2) = AffineGap.align(str1, str2)
    println(s1)
    println(s2)
  }
}
<file_sep>/src/main/scala/DebrujinGraph/Main.scala
package DebrujinGraph

object Main {
  def main(args: Array[String]): Unit = {
    val graph = new DebrujinGraph(5)
    println(graph.str)
    graph.cycle.zipWithIndex.foreach({ case (v, i) =>
      println(" " * i + graph.VString(v))
    })
    graph.saveDot()
  }
}
<file_sep>/src/main/scala/Hmm/Coin.scala
package Hmm

import Hmm.Aligner.Matrix

sealed trait Coin

case object Head extends Coin

case object Tail extends Coin

sealed trait State

case object Sym extends State

case object Unsym extends State

case class CoinHMM(pSymSym: Double, pUnsymUnsym: Double) {
  require(0 <= pSymSym && pSymSym <= 1)
  require(0 <= pUnsymUnsym && pUnsymUnsym <= 1)

  private val markovModel = Array(
    Array(pSymSym, 1.0 - pSymSym),
    Array(1.0 - pUnsymUnsym, pUnsymUnsym)
  )

  private val coinToP = Array(
    Array(0.5, 0.5),
    Array(0.9, 0.1)
  )

  private val toState: Array[State] = Array(Sym, Unsym)

  def Viterbi(coins: List[Coin]): List[State] = {
    val coinsInt: List[Int] = coins.map({
      case Head => 0
      case Tail => 1
    })
    val n = coins.size

    val dp: Matrix[Double] = Array.fill(n, 2)(0.0)
    dp(0) = Array(
      0.5 * coinToP(0)(coinsInt.head),
      0.5 * coinToP(1)(coinsInt.head)
    )

    val prev: Matrix[List[State]] = Array.fill(n, 2)(Nil)
    prev(0) = toState.map(x => List(x))

    for (i <- 1 until n) {
      val c: Int = coinsInt(i)
      for (j2 <- 0 to 1) {
        val (costMax, jMax) =
          (for (j1 <- 0 to 1)
            yield (dp(i - 1)(j1) * markovModel(j1)(j2) * coinToP(j2)(c), j1)
            ).max

        val state: State = toState(j2)

        dp(i)(j2) = costMax
        prev(i)(j2) = state :: prev(i - 1)(jMax)
      }
    }

    (if (dp(n - 1)(0) > dp(n - 1)(1)) prev(n - 1)(0) else prev(n - 1)(1)).reverse
  }

  def FB(coins: List[Coin]): List[Double] = {
    val coinsInt: List[Int] = coins.map({
      case Head => 0
      case Tail => 1
    })
    val n = coins.size

    val dpBefore: Matrix[Double] = Array.fill(n, 2)(0.0)
    dpBefore(0) = Array(
      0.5 * coinToP(0)(coinsInt.head),
      0.5 * coinToP(1)(coinsInt.head)
    )

    for (i <- 1 until n) {
      val c: Int = coinsInt(i)
      for (j2 <- 0 to 1) {
        dpBefore(i)(j2) =
          (for (j1 <- 0 to 1)
            yield dpBefore(i - 1)(j1) * markovModel(j1)(j2) * coinToP(j2)(c)
            ).sum
      }
    }

    val dpAfter: Matrix[Double] = Array.fill(n + 1, 2)(0.0)
    dpAfter(n - 1) = Array(1.0, 1.0)

    for (i <- (n - 2) to 0 by -1) {
      val c: Int = coinsInt(i + 1)
      for (j1 <- 0 to 1) {
        dpAfter(i)(j1) =
          (for (j2 <- 0 to 1)
            yield markovModel(j1)(j2) * coinToP(j2)(c) * dpAfter(i + 1)(j2)
            ).sum
      }
    }

    val coinsP = dpBefore(n - 1).sum

    def res(t: Int) = (for (i <- 0 until n) yield dpBefore(i)(t) * dpAfter(i)(t) / coinsP).toList
    res(0)
  }
}

object CoinHMM {
  def toCoins(s: String): List[Coin] = {
    s.map({
      case 'О' => Head
      case 'Р' => Tail
      case _ => throw new RuntimeException("unexpected char")
    }).toList
  }
}
<file_sep>/src/main/scala/Trees/PGMA.scala
package Trees

import Trees.Conversions._
import Trees.TreeBuilder.Matrix

import scala.collection.mutable

trait PGMA extends TreeBuilder {

  private case class Node(tree: Tree, size: Int = 1, height: Double = 0.0)

  private def join(a: Node, b: Node, dist: Double): Node = {
    val newHeight = dist / 2
    val newTree: Tree = TreeNode(Edge(a.tree, newHeight - a.height), Edge(b.tree, newHeight - b.height))
    Node(newTree, a.size + b.size, newHeight)
  }

  override def build(dist: Matrix, labels: Array[String]): Tree = {
    checkSizes(dist, labels)
    val d: Matrix = dist.map(_.clone)

    val nodes: Array[Node] = labels.map(name => Node(name: Leaf))
    val roots: mutable.Buffer[Int] = labels.indices.toBuffer[Int]

    while (roots.length >= 2) {
      val (minD, i, j) = (for {
        i <- roots
        j <- roots
        if i < j
      } yield (d(i)(j), i, j)).min

      val v: Int = i
      roots -= i
      roots -= j
      for (t <- roots) {
        val newD: Double = newDist(d(t)(i), nodes(i).size)(d(t)(j), nodes(j).size)
        d(t)(v) = newD
        d(v)(t) = newD
      }
      roots += v
      nodes(v) = join(nodes(i), nodes(j), minD)
    }
    nodes(roots.head).tree
  }

  def newDist(dist1: Double, size1: Int)(dist2: Double, size2: Int): Double
}

object WPGMA extends PGMA {
  override def newDist(dist1: Double, size1: Int)(dist2: Double, size2: Int): Double = {
    (dist1 + dist2) / 2
  }
}

object UPGMA extends PGMA {
  override def newDist(dist1: Double, size1: Int)(dist2: Double, size2: Int): Double = {
    (dist1 * size1 + dist2 * size2) / (size1 + size2)
  }
}
<file_sep>/src/main/scala/Hmm/Main.scala
package Hmm

import scala.io.StdIn
import Aligner.{Matrix, moves}

object Main {
  def printMatrix(matrix: Matrix[Double]): Unit = {
    matrix.foreach({lst =>
      lst.foreach(x => print(f"$x%.8f "))
      println()
    })
    println()
  }

  def main(args: Array[String]): Unit = {
    val s = "acgt"
    val t = "tgca"

    val markovModel = Array(
      Array(0.4, 0.3, 0.3),
      Array(0.4, 0.6, 0.0),
      Array(0.4, 0.0, 0.6)
    )

    val aligner = Aligner(markovModel,
                          initProbability = Array(1 / 3.0, 1 / 3.0, 1 / 3.0),
                          mismatchGenP = 0.1,
                          gapGenP = 0.3)

    val (s1, t1) = aligner.Viterbi(s, t)
    println(s1)
    println(t1)
    val resFB: Matrix[Double] = aligner.FB(s, t)
    printMatrix(resFB.map(_.drop(1)).drop(1))

    aligner.BacktrackFB(s, t)
  }

  def mainCoin(): Unit = {
    val coinHmm = new CoinHMM(0.8, 0.7)
    val s: String = StdIn.readLine() //  "ОРОРОРОООООО"
    val coins: List[Coin] = CoinHMM.toCoins(s)
    println(coinHmm.Viterbi(coins))

    println(coinHmm.FB(coins).map(x => (x * 10000).round / 10000.0))
  }
}
<file_sep>/src/main/scala/Alignment/Alignments.scala
package Alignment

trait Aligner {
  def match_score = 1
  def gap_penalty = 1
  def mismatch_penalty = 1
  def gap_open_penalty = 0

  def local: Boolean
  def weight(c1: Char, c2: Char): Int = if (c1 == c2) match_score else -mismatch_penalty

  private val inf: Int = 1e9.toInt

  def align(str1: String, str2: String): (String, String) = {
    val defult_dp = if (local) 0 else -inf

    val n = str1.length
    val m = str2.length

    val a = "\n" + str1.toLowerCase
    val b = "\n" + str2.toLowerCase
    type Array3D[T] = Array[Array[Array[T]]]

    val (gap_closed, gap_a, gap_b) = (0, 1, 2)

    val dp: Array3D[Int] = Array(
      Array.fill[Int](n + 1, m + 1)(defult_dp),
      Array.fill[Int](n + 1, m + 1)(-inf),
      Array.fill[Int](n + 1, m + 1)(-inf)
    )

    dp(gap_closed)(0)(0) = 0

    val res1: Array3D[List[Char]] = Array.fill[List[Char]](3, n + 1, m + 1)(Nil)
    val res2: Array3D[List[Char]] = Array.fill[List[Char]](3, n + 1, m + 1)(Nil)

    var mx: (Int, (Int, Int)) = (0, (0, 0))

    for (i: Int <- 0 to n; j: Int <- 0 to m; if (i, j) != (0, 0)) {
      def relax(k1: Int)(k2: Int)(i1: Int, char1: Char)(j1: Int, char2: Char)(add: Int): Unit = {
        if (i1 >= 0 && j1 >= 0 && dp(k1)(i1)(j1) + add >= dp(k2)(i)(j)) {
          dp(k2)(i)(j) = dp(k1)(i1)(j1) + add
          res1(k2)(i)(j) = char1 :: res1(k1)(i1)(j1)
          res2(k2)(i)(j) = char2 :: res2(k1)(i1)(j1)
        }
      }

      relax(gap_closed)(gap_closed)(i - 1, a(i))(j, '-')(-gap_open_penalty - gap_penalty)
      relax(gap_closed)(gap_closed)(i, '-')(j - 1, b(j))(-gap_open_penalty - gap_penalty)
      relax(gap_closed)(gap_closed)(i - 1, a(i))(j - 1, b(j))(weight(a(i), b(j)))

      relax(gap_closed)(gap_a)(i, '-')(j - 1, b(j))(-gap_open_penalty - gap_penalty)
      relax(gap_a)(gap_a)(i, '-')(j - 1, b(j))(- gap_penalty)
      relax(gap_a)(gap_closed)(i, '-')(j - 1, b(j))(- gap_penalty)

      relax(gap_closed)(gap_b)(i - 1, a(i))(j, '-')(-gap_open_penalty - gap_penalty)
      relax(gap_b)(gap_b)(i - 1, a(i))(j, '-')(-gap_penalty)
      relax(gap_b)(gap_closed)(i - 1, a(i))(j, '-')(-gap_penalty)

      if (dp(0)(i)(j) > mx._1)
        mx = (dp(0)(i)(j), (i, j))
    }

    val (res_n, res_m) = if (local) mx._2 else (n, m)
    (res1(gap_closed)(res_n)(res_m).mkString.reverse, res2(gap_closed)(res_n)(res_m).mkString.reverse)
  }
}

trait SimpleAlignment extends Aligner {
  override def local = false
}
object SimpleAlignment extends SimpleAlignment

trait LocalAlignment extends Aligner {
  override def local = true
}
object LocalAlignment extends LocalAlignment

object WeightedAlignment extends SimpleAlignment {
  def unknown_char_penalty = 100

  override def weight(c1: Char, c2: Char): Int = {
    val charMap: Map[Char, Int] = Map('a' -> 0, 'c' -> 1, 'g' -> 2, 't' -> 3)
    val weights: Array[Array[Int]] = Array(
      Array( 1, -1, -1, -1),
      Array(-1,  1, -1, -1),
      Array(-1, -1,  1, -1),
      Array(-1, -1, -1,  1)
    )
    (for {
      a <- charMap.get(c1)
      b <- charMap.get(c2)
    } yield weights(a)(b))
    match {
      case Some(x) => x
      case None => -unknown_char_penalty
    }
  }
}

object AffineGap extends SimpleAlignment {
  override def local = false
  override def gap_open_penalty: Int = 2
  override def mismatch_penalty: Int = 2
}

/*test
tccCAGTTATGTCAGgggacacgagcatgcagagac
aattgccgccgtcgttttcagCAGTTATGTCAGatc
*/<file_sep>/src/main/scala/Trees/Trees.scala
package Trees

sealed trait Tree {
  def newick: String
}

case class Leaf(name: String) extends Tree {
  override def newick: String = name
}

case class Edge(tree: Tree, len: Double) {
  def newickPart: String = tree.newick + ":" + len
}

case class TreeNode(edgeL: Edge, edgeR: Edge) extends Tree {
  override def newick: String = s"(${edgeL.newickPart},${edgeR.newickPart})"
}

case class RootedTree(seq: Seq[Edge], name: String) extends Tree {
  override def newick: String =
    if (seq.nonEmpty) {
      seq.map(_.newickPart).mkString("(", ",", ")") + name
    } else {
      name
    }
}

object Conversions {
  implicit def leaf(name: String): Leaf = Leaf(name)
}

languages: Markdown Scala

repo_name: maxkvant/BioAlgCourse


text:
<repo_name>rajlohith2/Weather-website<file_sep>/views/about.hbs

{{text}}

Gives you weather data if you type in a place

<file_sep>/views/partials/footer.hbs

Created as a practise while learning node

branch_name: refs/heads/master

repo_language: Handlebars