Date |
Mar 19, 2014 |
Speaker |
Dr. Tetsuo Shibuya
|
Title |
de Bruijn Graph Problems
|
Abstract |
DNAアセンブリアルゴリズムは非常に大きなメモリを要するが、その理由は、それらの多くのアルゴリズムが基づいているde Bruijn graphというグラフが非常に巨大であるためである。しかし、過去3年ほどでde Bruijn graphを小さく保持する技術が飛躍的に発展した。本セミナーでは、そのようなde Bruijn graphを小さく保持する新しい技術である、succinct de Bruijn graphとよぶ新たなデータ構造を紹介する。また、de Bruijn graphはたとえ小さく保持してもグラフは巨大なものであるため、複雑な処理を行うことが難しいことが多い。本セミナーでは、de Bruijn graphのグラフの性質を用えば、通常は難しい複雑な解析が可能になる場合があることを紹介する。
|
|