Markov Cluster Algorithm を Ruby & NArray で実装

NGSデータを用いたde novo assemblyにはクラスタリングアルゴリズムが重要であろう，という妄想からふらふらとクラスタリング法を調べていて見つけたのがMCLことMarkov Cluster Algorithm．2000年に発表された手法らしく特に新しい分けではないが，それなりに性能は良いらしいとか．

詳しい説明は本家ホームページ（MCL - a cluster algorithm for graphs）に丸投げしさっそく実装を行ってみた．こちらのサイトに（2010-06-28 - (setf yaruki nil) - nlpyutoriグループ）rubyの実装例があったのだが，NArrayを使いたい！と思いNArrayバージョンとして実装してみた．

タブ区切りで，edgelistを作り第一引数に，全ノード数を第二引数に与えて実行するというダサい形．最終的にはm1行列からクラスター情報を取り出す必要があるが，まだ実装しておりません．．下記テストデータを与えると瞬間でクラスタリングが終了！多分まともな答えが出ている気がします．

#!/usr/local/ruby1.9.2/bin/ruby19
require "rubygems"
require "narray"

def main
  # parameters
  file = ARGV.shift
  size = ARGV.shift.to_i
  r    = 2.0
  th   = 0.00001
  
  # read graph
  m1 = NMatrix.float(size, size)
  File.foreach(file) do |line|
    i, j = line.chomp.split("\t")
    m1[i.to_i, j.to_i] = 1
    m1[j.to_i, i.to_i] = 1
  end
  m1.I
  m1.div!(m1.sum(0))
  
  # MCL
  loop do
    m2 = m1**2                              # expansion
    m1 = NMatrix.refer(NArray.refer(m2)**r) # inflation
    m1.div!(m1.sum(0))                      # inflation
    dif = (NArray.refer(m1-m2)**2).sum
    break if dif < th
  end
  
  # output
  p m1
end

main if __FILE__ == $0

テストデータ．こちらを参考にさせていただきました（Fig. 2 http://www.matlab.nitech.ac.jp/~matsuo/NL05-1.pdf）．

5	9
0	5
0	9
0	6
6	9
0	1
4	6
1	4
1	2
2	4
4	7
2	3
3	7
7	10
7	8
3	10
3	8
8	10
8	11
10	11

いったい何者なのだろうか

という，素直な疑問に答えてくれる．会社に入るまで一般社員と管理職という二元組織になっていることすら知らなかった私に，課長という存在の意義，平社員，経営職のどちらとも違う仕事の性質を教えてくれる．課長が元気な会社が繁栄する，というのは何か分かる気がするな．

はじめての課長の教科書

歴史小説？！ナニソレ美味しいの？

ってくらいのわたくしが，今読んでいるのがこれ．初めは地名やら役職やら，同じ人物なのに幾つもの呼ばれ方をしてたりと混乱の極みだった訳だがようやく慣れてきて面白くなってきた．ストーリー展開も速いし，これは最後まで読めるかも知れん．全4巻読破目指しマッスル．

楽毅（一） (新潮文庫)

誘拐と魔性のゲイと天然素材，そして影の話

絶対自分では読まないだろう作品を次々と貸してくれる同僚に感謝．今回は西洋骨董洋菓子店，アンティークである．GAYネタが絡むということで用心していたが，全3巻綺麗にまとまった，むしろ続きを読みたいと思わせる作品．魔性のゲイが降りだした雨の中飛び出してのポーズ！そして男ふたりでのダンス，なんだかバカげてて笑ろてもーたのでした．．意外とオススメ．

西洋骨董洋菓子店 (1) (ウィングス・コミックス文庫)

カレーを食いつつ華麗を読む

同僚に全37巻を借り読破中．作者の並々ならぬ女性キャラへの執着を感じる作品(コミック本の表紙裏は全て作中女性キャラの入浴等セクシーショットが描かれている)．またバクマンを読んだ後だと，なんとも少年誌のヒット作にあるべき要素が組み込まれているのが分かる，すなわち「特殊能力を持った主人公」，「強力なライバルの存在」，「バトル」，「パンチラ等の微エロ」，「ヒロインとの恋愛」．まさに最強なり(笑)

華麗なる食卓 1 (ヤングジャンプコミックス)

ナツイチストラップゲットingデバイス

乙一ということで読んでみた，乙一のお話に古屋兎丸が作画した合作．うわぁ若いなぁー…でも何か分かる的な情緒不安定な高校生たちの話がオムニバス形式で進み，最後に全員登場でクライマックスどーん．中高生の頃の何かモヤモヤした焦りのような気持ちを思い起こす一作・あの頃の気持ちを忘れてしまい，そしてそれを思い出してみるのも一興と思える人必読．

少年少女漂流記 (集英社文庫)

ローマの風呂建築家という発想

これは笑える！久々に誰もいない空間に向かって爆笑してしまった．ローマの風呂建築家がタイムワープし日本の風呂文化からヒントを得て，ローマ社会で成功していくという謎のサクセスストーリーってところか．「平たい顔族」であることを誇りに思える一冊．そして聖☆おにいさんがイケる口なら間違いなく爆笑・なんかそんな気がする名作．

テルマエ・ロマエ I (BEAM COMIX)

聖☆おにいさん(1) (モーニング KC)