2013年前半振り返り
暑い日々が続きますが、いかがお過ごしでしょうか？ 早いもので2013年もう８月ということでだいぶ遅いですが2013年の前半の成果を振り返ってみたいと思います。幸いにも2013年の前半に4本論文を出す事ができました。内分けは、データマイニング・機械学習1本、バイオインフォマティクス1本、 文字列処理２本となります。以下では１つ１つ論文の内容を簡単に紹介していきたいと思います。
Yasuo Tabei, Akihiro Kishimoto, Masaaki Kotera, Yoshihiro Yamanishi: Succinct Interval Splitting Tree for Scalable Similarity Search of Compound-Protein Pairs with Property Constraints, 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2013 論文PDFへのリンク
データマイニングと知識発見に関するトップ国際会議SIGKDD2013の論文。内容は、化合物・タンパク質ペアーを高速検索するための簡潔データ構造を提案したというもの。化合物・タンパク質ペアーはフィンガープリント(バイナリーベクトル)として表現できる。一方、化合物・タンパク質ペアーは実数値で表現される性質 (例えばLogP値, タンパク質の表面積など)を持つ。よって、タンパク質・化合物ペアーの検索問題はクエリーに対して(i)フィンガープリントが似ているかつ(ii)性質が似ているペアーをデータベースからすべて発見する問題として定式化できる。近年の、ドラッグ・ターゲット相互作用データベースの登場そして大規模化によりこの問題はますます重要度を増しています。たとえば、今回扱ったドラッグ・ターゲット相互作用データベースは約２億の相互作用を含みます。一方、フィンガープリントの検索問題は、データマイニングとケモインフォマティクスの分野で非常に良く研究されているが、(i)フィンガープリントの類似度にだけに基づく手法に対しては大規模データベースにたいしては検索速度に問題があり使い物になりません。そこで、(i)と(ii)の類似度にもとづき化合物-タンパク質ペアーを高速検索するための簡潔データ構造を提案しました。提案手法は(i)のフィンガープリントの類似度に基づく手法よりも100-1000倍高速に検索することができます。
KDD発表日とある面接日が8月12日と重なってしましい、東京で面接受けてすぐにシカゴに飛んで自分の発表の15分まえに会場に到着して研究発表するという無茶をやってのけました。これは一生忘れない....
Masaaki Kotera, Yasuo Tabei, Yoshihiro Yamanishi, Toshiaki Tokimatsu, Susumu Goto: Supervised de novo reconstruction of metabolic pathways from metabolome-scale compound sets, ISMB/ECCB2013. 論文へのリンク
バイオインフォマティクスに関するトップ国際会議ISMB/ECCB2013の論文。内容は代謝ネットワークを化合物集合から再構築する手法を開発したというもの。主な工夫点は、化合物ペアーからネットワークを高精度に予測するための解釈可能な特徴量を作ったところで、この特徴量とスパース分類器を組み合わせることにより、ネットワークを高精度に予測しつつ、予測に貢献する化合物の部分構造を抽出することに成功している。
ISMB/ECCBに参加したのは2007年の6年ぶりでした。分野はだいぶdivergeしている印象でした。
Yasuo Tabei, Yoshimasa Takabatake, Hiroshi Sakamoto: A Succinct Grammar Compression, 24th Annual Symposium on Combinatorial Pattern Matching (CPM), 2013. 論文(PDF)へのリンク
文字列パターンマッチングに関する国際会議CPM2013の論文。主な内容は文法圧縮されたテキストをエンコーディングする際の情報論的下限を示したというもの。証明の際には、DAGのスパニング木分解、順序木の列挙など技をいろいろ使っています。その他、提示した情報論的下限を漸近的に達成するエンコーディング法も提示しています。
Shirou Maruyama, Yasuo Tabei, Hiroshi Sakamoto, Kunihiko Sadakane: Fully-Online Grammar Compression, 20th String Processing and Information Retrieval Symposium (SPIRE), 2013.
文字列と情報検索に関する国際会議SPIRE2013の論文。本論文では圧縮サイズがCPM2013で示した情報論的下限を漸近的に達成するオンライン文法圧縮を提示しました。提案法により文字列をオンラインで読みつつ、直接的に簡潔表現にエンコードする(Fully-Online)ことができます。簡潔表現では部分文字列復元もサポートしています。
GW前に締め切りが延期されたこともあって急遽仕上げることになった論文で、GW中ずっと篭って論文書いていました。共著者の皆様にはご迷惑をお掛けしました。
