Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう?と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き
ref: http://portal.acm.org/citation.cfm?id=1582723大規模グラフ処理フレームワーク Pregel の論文を読み, BSP (Bulk Synchronous Parallel) モデルで実装したいグラフのアルゴリズムがいくつかあったのでオープンソース実装を探してみた. GoldenOrb, Phoebus, HAMA (汎用的なBSP model), そして Bagel などいくつかの実装があるようで, GoldenOrb は Java, Phoebus は Erlang で実装されており, Bagel は Scala で書かれている. Bagel は Spark 上で動くシンプルな実装 (たったの 150 行程度) で, 大規模なタスクに対してもスケールする運用が可能に思えたので Bagel を使ってみることにした. (Phoebus は
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く