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

目次はこちら
離散アルゴリズムは数値アルゴリズムと並び立つもの。数値アルゴリズムは前章のEMもそうだし、固有値分解もそう。離散データには離散アルゴリズム
2.1 Tropical arithmetic と動的計画法
- 動的計画法はだんだんに必要なものを積み上げて解に到達する方法
- この動的計画法を代数的構造として構成するのに便利なのがトロピカル半環
- トロピカル半環は実数に∞を加え、２つの演算(最小値を取る、和を取る)を考慮した構造( $(\mathbf{R} \cup \{\infty\}, \oplus,\odot)$ )
- 重み付き有向グラフのノード間最短距離は隣接行列のトロピカル半環の演算のべき乗で表すことができる、というような使い方をする
- 整数計画問題(integer linear programming)でもグラフの隣接行列とトロピカル半環演算として扱うことができる。トロピカル半環的な行列式、なども登場する
- 割り付け問題ではトロピカル半環的行列式を使うそうだ(参考：割り付け問題)
2.2 シーケンスアラインメント(配列を並べること)
- シーケンスアラインメントにトロピカル演算を用いて代数統計モデル化する
- 格子とその一方向対角線でできたグラフにモデル化できる。そのグラフがトロピカル演算の性質を持つ(？)
2.3 ポリトープ(多角形の一般次元化)
- 離散的データなので凸ポリトープとして取り扱えて、その上の適切な点の探索ととらえる
2.4 木と距離函数
- 系統樹という木と距離の保存、Neighbor-Joining
2.5 ソフトウェア
- 数学ソフト
  - "4TI2"
    - 非負整数の線形代数。トーラスモデルに有用
  - LAPACK/SVDPACK
    - 線型代数のFORTRAN ライブラリ、SVD(Singular value decomposition)のライブラリ
  - "MACAULAY2"
    - 代数幾何・可換環論のソフトウェア系
  - "MAGMA"
    - 代数、幾何、組み合わせ構造(グラフ・群環体)、グレブナー基底計算のソフトウェア
  - "MAPLE"
    - 計算機数学の汎用ソフト
  - "MATHEMATICA"
    - 計算機数学の汎用ソフト
  - "MATLAB"
    - 計算機数学の汎用ソフト、特に線形代数計算
  - "POLYMAKE"
    - ポリトープの取り扱い
  - "SINGULAR"
    - 多項式、可換環論、計算機代数幾何。代数統計にとても便利
  - "R"
    - 数学者にとってMATLAB相当。バイオコンダクタもお奨め
- 生物用途ソフト
  - "BLAST"
  - "MAVID"
  - "PAML"
  - "PHYLIP"
  - "SPLITSTREE"