de Bruijn Graph を使った de novo アセンブリの発想がすごい件 - ほくそ笑む
Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう？と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き
日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念 - アジマティクス
Ｑ：これは何の構造を表しているでしょう？ グラフ理論 上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。 （余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ ○○」や「グラフ理論 ○○」とググるよりも、「ネットワーク ○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています） さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例
Boost.GraphでJR全線乗り尽くしプランを立てる - プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 （2014.7.12）
Boost.GraphでJR全線乗り尽くしプランを立てる - プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 （2014.7.12）
橋（bridge）検出アルゴリズム - nupiocaの日記
連結グラフにおいて橋（bridge）とは、それを取り除くと連結でなくなってしまうような辺のこと。閉路に含まれない辺が橋になる。 橋はDFSを行うことで検出することができる。DFSは、アルゴリズムの一部としてグラフの構造を調べる時によく使われる。 アルゴリズム まず、頂点を１つ選び、DFSを開始する。 各頂点には、pre、lowという２つのデータを記録する。 preは、DFS木の行きがけ順（pre-order）の値を保持する。 lowは、DFS木でその頂点から到達しうる頂点のpreの最小値を保持する。初期値はその頂点のpreである。 次の頂点が、すでに訪れてある（preの値が存在する）場合は、自分のlowを、次の頂点のlowと比べて小さい方に更新する。 次の頂点をまだ訪れていない場合は、その頂点に対してDFSを続ける。そして、その頂点へのDFSが終了した際に、lowがpreより小さくなってい
手続き型言語OCaml - fetburner.core
この記事はML Advent Calendar8日目の記事として書かれました。 7日目の記事はでこれきさんのfoldみぎひだりです。 Standard MLやOCamlをはじめとしたML系の言語は関数型言語として有名ですが、参照、配列、例外といった副作用を伴う機能も扱う事ができます。 また、ML系の言語で手続き的に書いたからと言ってその言語の魅力が損なわれるわけではなく、 強い静的型付け、型推論やparametric polymorphismなどの恩恵を受けられるので、むしろ良く設計された手続き型言語のように映る事でしょう。 積極的にMLで手続き的な処理を書いていこうな。 2015年12月8日1:05 Kleene's algorithmの実装を間違えていたので修正 2015年12月8日17:54 プログラムの例をリファクタリングした 手続き的な処理と言えば僕はグラフ関連のアルゴリズムが思
Go + QML + QChart.js で素敵なチャートを表示する - Qiita
「Go + QML + QChart.js で素敵なチャートを表示する - Goとキュート(Qt)な日々」から転載。 Go と QML と QChart.js を使って素敵なチャートを表示してみます。 QChart.js とは QChart.js とは、jwintz/qchart.js · GitHubで開発されているQMLでチャートを表示するためのJavaScriptライブラリです。 画像はjwintz/qchart.js · GitHubのREADME.mdより引用 環境 go version go1.5.2 darwin/amd64 Qt 5.5.1 OS El Capitan 準備 jwintz/qchart.js · GitHubからQChart.jsのプロジェクトごとダウンロードしてきます。 ドキュメントのSetupの項目では自分のgitプロジェクトにサブモジュールとして追加す
FP Graph Algorithms
Manipulating graphs has traditionally been seen as a place where imperative programming reigns supreme. Tikhon Jelvis begs to differ, and shows a trick where graph traversal can be expressed by a form of pattern matching. After explaining the approach he simulates how it works on a sample graph. Summary Traditionally graph algorithms are seen as one of the things that are really hard in functional
Homomorphisms of Graphs
グラフ準同型のはなし グラフの準同型って何？ 完全グラフへの準同型：グラフの彩色 クネーザーグラフへの準同型：グラフの分数彩色 トーナメントグラフへの準同型：非巡回性 有向パスへの準同型：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
The Monad.Reader/Issue5/Practical Graph Handling - HaskellWiki
This article needs reformatting! Please help tidy it up.--WouterSwierstra 14:26, 9 May 2008 (UTC) A Practical Approach to Graph Manipulation by JeanPhilippeBernardy for The Monad.Reader Issue 5 BR Date(2005-07-08T20:48:51Z) Abstract. Tree-based data structures are easy to deal with in Haskell. However, working with graph-like structures in practice is much less obvious. In this article I present a
いちからはじめる GMT - index
2011年 3月 1日 更新 GMT（The Generic Mapping Tools）は高機能の地図・グラフ作成，データ処理ツール群である． 使いこなせば強力なツールであるが，対話的でない， コマンドがたくさんある，オプションがやたらと多いなど初心者には取っつきにくいツールでもある． 「いちからはじめる GMT」は，最小限のコマンド，オプションからはじめて， 少しずつ複雑にしていくことで， GMT の使い方を初歩から学んでもらおうと思って書いていく． たくさんあるコマンド，オプションをちょっとずつ覚えていってもらいたい． 使用した GMT のバージョン その1〜35：4.2.1 その36〜38：4.5.3 その39〜：4.5.5 2011年 いちからはじめる GMT その41 - psxy -A （2011年 3月 1日 掲載） いちからはじめる GMT その40 - -Jm（メルカト
大規模グラフ処理フレームワーク Pregel のオープンソース実装 Bagel とか - Standard ML of Yukkuri
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 は
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
de novo アセンブリー | de Bruijn graph によるゲノムアセンブリー
Redirect
http://www.mathgram.xyz/entry/plotly
x=yz^2 graph - Wolfram|Alpha
A Neighborhood of Infinity: How to write tolerably efficient optimzation code without really trying...
Haskell for Maths