タグ

algorithmとngsに関するma_koのブックマーク (5)

  • https://www2.informatik.hu-berlin.de/~hakenber/links/nextgen.html

    ma_ko
    ma_ko 2011/05/30
    6月入ったらざっと見るか。IBD とか需要ある。
  • de Bruijn Graph を使った de novo アセンブリの発想がすごい件 - ほくそ笑む

    Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう?と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き

    de Bruijn Graph を使った de novo アセンブリの発想がすごい件 - ほくそ笑む
  • BWT と PPM - naoyaのはてなダイアリー

    Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は質的に同じ事をやっている、というお話です。 先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。 サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると質的に同じことをやっていると言える、というところです。 BWT のあら

    BWT と PPM - naoyaのはてなダイアリー
    ma_ko
    ma_ko 2010/01/25
    "文脈でソートした BWT 後のテキストは、同じ文字が連続して出現しやすい"のくだりが分かりやすかった
  • Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー

    ,. -‐'''''""¨¨¨ヽ (.___,,,... -ァァフ|          あ…ありのまま 今日 起こった事を話すぜ! |i i|    }! }} //| |l、{   j} /,,ィ//|       『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ、_ノ/ u {:}//ヘ |リ u' }  ,ノ _,!V,ハ | /´fト、_{ル{,ィ'eラ , タ人        な… 何を言ってるのか わからねーと思うが /'   ヾ|宀| {´,)⌒`/ |<ヽトiゝ        おれも何をされたのかわからなかった… ,゙  / )ヽ iLレ  u' | | ヾlトハ〉 |/_/  ハ !ニ⊇ '/:}  V:::::ヽ        頭がどうにかなりそうだった… // 二二二7'T'' /u' __ /:::::::/`ヽ /'

    Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
  • ブロックソート - Wikipedia

    ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。 ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。 実装はbzip2等。 Python言語による実装例が文献[1]に出ている。 長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n

  • 1