Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう?と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き
グラフ準同型のはなし グラフの準同型って何? 完全グラフへの準同型:グラフの彩色 クネーザーグラフへの準同型:グラフの分数彩色 トーナメントグラフへの準同型:非巡回性 有向パスへの準同型:balanced graph 準同型の合成 準同型が存在しない条件 準同型同値とcore グラフ準同型に関する入門者用の紹介記事です。 参考文献としては、 P. Hell and J. Nesetril, 「Graphs and Homomorphisms」(Oxford University Press) 2004. C. Godsil and G. Royle, 「Algebraic Graph Theory」(Springer-Verlag) 2001. などがあります。他に, E.R.Sheinerman & D.H.Ullman, 「Fractional Graph Theory」(John W
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く