第53回プログラミング・シンポジウムでデモを発表しました

はじめに

　明けましておめでとうございます．大野です．1月6日から8日にかけて情報処理学会の第53回プログラミング・シンポジウムが行われ，私も参加しました．

　私自身は今回が初参加で，どのような会なのかは全く検討がつかなかったのですが，一日中どこかで議論が行われていている，頭の休まらない3日間でした．また，一方的にしか存じ上げていなかった方などとも直接お話ができたのも貴重な機会でした．シンポジウムを企画・運営していただいた方々には感謝しております．

今回行ったデモについて

　さて，今回のシンポジウムで，会社内のチームで開発したデモの発表を行いました．今回のブログではその際の説明で用いたポスター資料を掲載して，簡単に補足を行おうと思います．特にデモの検索画面は当日見ていただいたので，それではあまり触れられなかった内部のアルゴリズムについて詳しく解説します．

今回発表したのは，塩基配列の曖昧検索のデモンストレーションです．デモのポイントは次の3つです

• ヒトの全塩基配列に対し，10000塩基中2000塩基が異なる塩基配列の全列挙でもそれなりの所要時間（100秒程度）で動くアルゴリズムを考案した
• それをライブラリとして実装し，使用するサーバーを作成した
• 検索結果を閲覧するUIを実装した（このUIはjs_of_ocamlを用いて作成しました）

問題設定とアルゴリズム

　考える問題設定は単純で，「文字列\(\mathrm{T}\), 検索クエリ\(q\), 許容誤差\(d\)が与えられたとき，\(\mathrm{T}\)の部分列で，\(q\)との編集距離が\(d\)以下のもの全列挙せよ」というものです．これをSuffix Arrayと分割統治法を用いて解きます．

　アイデアの基礎となるのは次の事柄です：パターン\(\mathrm{P}\)と文字列\(\mathrm{S}\)の編集距離が\(d\)以下とします．すると\(\mathrm{P}\)と\(\mathrm{S}\)を半分に分割し，それぞれを\(\mathrm{P_{1}P_{2}}\)と\(\mathrm{S_{1}S_{2}}\)と書けば，「\(\mathrm{P_{1}}\)と\(\mathrm{S_{1}}\)の編集距離」と「\(\mathrm{P_{2}}\)と\(\mathrm{S_{2}}\)の編集距離」のうち少なくとも一つは\(d/2\)以下でなければなりません．

　そこで，各整数\(n\)に対しパターンを\(2^{n}\)個に分割し，それぞれのブロックに対し\(d/2^{n}\)だけ編集距離が離れた\(\mathrm{T}\)の部分列を見つける事をまず第一の目標とし，\(n\to n-1\to \cdots \to 1\to 0\)と値を減らしながらで帰納的に答えを求めます

　\(n\)が十分大きい場合（つまり，許容される編集距離が小さい場合）は，パターンの部分列と編集距離が小さいパターン達を列挙し，それらが文字列の中でどの位置にあるかをSuffix Arrayを用いて検索する事で解決します．一方，\(n\)が一般の場合には，元のパターンと編集距離が\(d/2^{n}\)以下の部分列が分かっているので，それを”種”とし編集距離が\(d/2^{n-1}\)以下の部分列に延ばせるかを調べる事で帰納的にパターンを列挙します．
　実際には細かい最適化をいくつか行っていますが，以上が大まかなアルゴリズムです．

デモ構成

　デモは2台のサーバーと検索結果を確認するUIで構成されています．

　サーバーはクエリを処理するフロントエンドサーバーと，インデックスと曖昧検索ライブラリを用いて実際に検索を行うバックエンドサーバーに分かれています．2つのサーバーの間の通信にはMessagePack RPCを用いています．

　UIはフロントエンドサーバーにHTTP経由でクエリを投げ，結果を一覧で表示する機能を持ちます．また，UI上で表示されるスニペット（クエリにヒットした部分列とその周辺部分を切り取った文字列）に対し，文字の置換・挿入・削除の様子を表示しています．

実験と結果と考察

　実験は上に挙げたデモ環境ではなく，バックエンドサーバーに相当するマシン1台で行いました．CPUはIntel Corei7，メモリは8GBです．ヒトのすべての染色体（1〜22番, X, Y）に含まれる塩基を連結した文字列を検索対象の文書としました．

　変化させるパラメータはパターン長(前述の問題設定の\(|q|\))と許容誤差率（\(|d|/|q|\)）の2つです．各パラメータについて，検索対象の文書からランダムに取り出した部分列を検索クエリとして検索時間を測定する事を10回行い，その平均をプロットしています．詳しい実験結果はポスターをご覧になってください．

　実験から分かった事をいくつかの事がわかりました．

• 許容誤差率が一定の条件下では，検索時間はパターン長に対して下に凸なグラフになっています．パターン長が短かければ候補が多くなる事で全体の検索時間が長くなり，長ければ一つ一つ部分列をチェックするのに時間を要する事で長くなると予想でき，今回の結果はこの予想と合致しています．
• 特にパラメータ設定のうちの1つに注目してみると，10000塩基の検索クエリに対し，許容誤差を20%を認めても100秒以内で全列挙が可能という結果が得られました．
• パターン長を固定したとき検索時間は許容誤差率に対して指数関数的に増加しています．許容誤差率に対して，検索ヒット数は指数関数的に増加すると予想できるので，今回のアルゴリズムでは許容誤差を大きくする事によるオーバーヘッドがないと期待できます．
• 本当にそれが正しい事を検証するには，許容誤差に対する検索時間の増加率と検索ヒット数に対する検索時間の増加率を比較しなければならないです．

コメント

　デモ発表の際，多くの方からコメントを頂きました．一例を挙げると，次のようなものです．

• 分割統治法で解いているならば容易に並列化できそう
• 全部オンメモリでインデックスが持てるならば，すべての部分列を愚直に計算する方法に比べてどのくらい性能に差が出るか？
• 許容誤差20%の違いを検索できる！というのはDNAの塩基配列を調べる事でどのくらいうれしい事なのか？（例えばヒトとネズミで同じ遺伝子で塩基配列の違いはどのくらいあるか）
• パターン長が同じでも，検索クエリによって検索時間の差が大きい．検索ヒット数も考慮に入れるのが良いのではないか？

まとめと今後の展望

　今回は塩基配列の曖昧検索を行うデモを作成し，そのアルゴリズム，デモサーバー構成，実験・結果・考察について説明しました．

　文字列操作の生物学での応用として塩基配列の検索は比較的容易に思いつく問題で，今回もその例の一つとして曖昧検索を行いました．しかし，具体的にバイオインフォマティックスや生物化学の分野でどのように問題設定を行うのがリーズナブルなのかについての知見を持っておらず，この曖昧検索をどのように応用すれば良いのかは模索している最中です．ご意見を頂けるとうれしく思っています．