Part I(基礎)2計算機科学 ぱらぱらめくる『Algebraic statistics for computational biology』

  • 目次はこちら
  • 離散アルゴリズムは数値アルゴリズムと並び立つもの。数値アルゴリズムは前章のEMもそうだし、固有値分解もそう。離散データには離散アルゴリズム
  • 2.1 Tropical arithmetic動的計画法
    • 動的計画法はだんだんに必要なものを積み上げて解に到達する方法
    • この動的計画法代数的構造として構成するのに便利なのがトロピカル半環
    • トロピカル半環は実数に∞を加え、2つの演算(最小値を取る、和を取る)を考慮した構造((\mathbf{R} \cup \{\infty\}, \oplus,\odot))
    • 重み付き有向グラフのノード間最短距離は隣接行列のトロピカル半環の演算のべき乗で表すことができる、というような使い方をする
    • 整数計画問題(integer linear programming)でもグラフの隣接行列とトロピカル半環演算として扱うことができる。トロピカル半環的な行列式、なども登場する
    • 割り付け問題ではトロピカル半環的行列式を使うそうだ(参考:割り付け問題)
  • 2.2 シーケンスアラインメント(配列を並べること)
    • シーケンスアラインメントにトロピカル演算を用いて代数統計モデル化する
    • 格子とその一方向対角線でできたグラフにモデル化できる。そのグラフがトロピカル演算の性質を持つ(?)
  • 2.3 ポリトープ(多角形の一般次元化)
    • 離散的データなので凸ポリトープとして取り扱えて、その上の適切な点の探索ととらえる
  • 2.4 木と距離函数
    • 系統樹という木と距離の保存、Neighbor-Joining
  • 2.5 ソフトウェア