演習IIIでは最先端の研究に触れるために、以下の課題を提供します。
研究途上にある課題のため、完成することが目的ではなくて、 むしろ研究の過程を試行錯誤しながら体験することが目標になります。
■ データマイニング
知能システム論で講義したアルゴリズムを使って ACM KDD Cup 2001 で出題された "Genomics Challenge" のデータに取り組みます。データ入手先は、
http://www.cs.wisc.edu/~dpage/kddcup2001/
優勝チームが使った方法や、コンテストの問題を解説した論文の PDF ファイルは ここ にあります。
もしくは ACM KDD Cup 2002 (今年もテーマは遺伝子データマイニング,4/29-6/26開催)に出場してみることも可能です。サイトは
http://www.biostat.wisc.edu/~craven/kddcup/
■ ヒトゲノム解析
ヒトゲノム解読以降、様々な生物種のゲノム解読には whole genome shotgun 方式が低コストであるため注目されていますが、この方式を実現するにはソフトウエアによるアセンブリ技術が不可欠です。しかし、長さが1億を超えるゲノムを正確かつ現実的な時間内に処理できるソフトはほとんど無いのが現状です。文献を読み、実装を試みることが課題です。
ARACHNE: A Whole-genome shotgun assembler (PDF File)
テストデータ(笠原君 mkasa@gi.k.u-tokyo.ac.jp)
ただ、上の論文を読んで、自ら定式化して、プログラムがかけるまで頑張るのはかなりしんどいようなので、第三期では以下の本の第4,5章を読んで、whole genome shotgun について理解を深めるということでもよいです。無論、我こそはと思う人は上の論文読解に挑戦してもよいです。
Pavel A. Pevzner: Computational Molecular Biology, An Algorithmic Approach (コピーは差し上げます)
■ Web データ解析
1) 同じキーワードを複数のサーチエンジンに投げると戦略が違うため異なるランキング結果が返ってきます。これらのランキング結果の間の距離を、視覚的に表現しサーチエンジンの差を描出するシステムを作成するのが課題です。この課題は王君が平成13年度の卒業論文で取り組みましたが、面白い課題なのでもう一度出します。
2) 2年以内にデータベースやWWWに関する国際会議や雑誌で公表された論文の中から興味ある論文を選んで精読します。文献が提案する方法の限界を見極めることをともに考えます。できたら実装して評価までできるとよいです。
ACM SIGMOD, ACM PODS, ACM SIGKDD (以上は http://www.acm.org/dl/ ) VLDB, WWW 等の会議録から選んでください。
推薦論文
Ashraf Aboulnaga, Alaa R. Alameldeen, Jeffrey F. Naughton: Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. VLDB 2001: 591-600 PDF file
Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan: Archiving Scientific Data. SIGMOD Conference 2002 PDF file