GGGenome開発メモ：大規模検索

windowmoon＠𝕏 @windowmoon

ゲゲゲノムのアルゴリズム解説とかソースコードってないのか？ローカル配列をデータベースにした検索はできない？

Nakazato T. @chalkless

@windowmoon RTしたので開発者本人も認識すると思いますが、 github.com/meso-cacase/GG… にちょこっと書いていますね。論文では兄弟サービスの ncbi.nlm.nih.gov/pubmed/22641850 くらいでしょうか。（参考にはならないかもですが

meso_cacase @meso_cacase

@windowmoon GGGenomeの詳しいアルゴリズムは未発表ですが、塩基配列のインデックスとして接尾辞配列およびFM-indexをSSDに保持し、鳩の巣原理と分割統治法を使って指定した数以内のミスマッチや挿入欠失を含む配列を見落としなく検索しています。

meso_cacase @meso_cacase

@windowmoon GGGenome内部の文字列検索エンジンは、PFI社（現レトリバ社）の開発した商用コードを含むため今のところオープンソースとして公開する予定はありませんが、ローカルでも検索できるようなパッケージを将来レトリバ社が有償にて提供するかもしれません。

windowmoon＠𝕏 @windowmoon

@meso_cacase ありがとうございます。おおよそわかりました。原理的に漏れが生じないはずなので、プライマーの検索には役立ちそうです。縮重塩基を受け付けてくれるところも素晴らしい。Primer-BLASTみたいなサービスがあれば是非使いたいのですが、現状では両プライマーの検索結果を処理しないといけませんね。

meso_cacase @meso_cacase

@windowmoon なるほど、特異性の高いPCRプライマーの設計ですね。公開されたゲノムであれば、GoogleスプレッドシートあたりからGGGenome APIを叩いて非特異的なヒットの件数を取得しまくれば、良い組み合わせを簡便に選択するようなことができるかもしれません。

meso_cacase @meso_cacase

@windowmoon 目的は異なりますが、表計算ソフトからGGGenome APIを叩いて配列検索する例です docs.google.com/spreadsheets/d… エクセルでもWin版2013以降であればWEBSERVICE()関数が使えると思います。

windowmoon＠𝕏 @windowmoon

@meso_cacase メタゲノム・環境DNA用プライマーの特異性・ユニバーサリティの評価をしたいので、ddbj112*全ての結果を(できれば並列的に)取得してスクリプトで処理するようなことを考えていますが、サーバは負荷に耐えられるでしょうか。攻撃と誤認されてブロックされることもありそうに思います。

meso_cacase @meso_cacase

@windowmoon メニューで選択できる配列DBごとに1つのデーモンが立っていて、ひとつのデーモン内ではリクエストを1つずつ順番に処理しているため、結果が返ってきてから次のクエリを発行してください。異なるDBに対しては同時にクエリを発行しても大丈夫なはずです。

meso_cacase @meso_cacase

@windowmoon もしサイトが重くなってきたりしたら、少しクエリ間隔をあけるようにしていただければと思います。かなり重そうですが、私も興味があるのでぜひ試してみてください。

windowmoon＠𝕏 @windowmoon

@meso_cacase ありがとうございます。とりあえずやってみます。

windowmoon＠𝕏 @windowmoon

@meso_cacase ミスマッチ許容量を限界まで大きくすると、タイムアウトしてしまいます。また、ミスマッチ0のとき、htmlは即座に表示できるのに、txt/csvだとタイムアウトしてしまいます。

windowmoon＠𝕏 @windowmoon

@meso_cacase txt/csvを落とそうとすると、「### ERROR : searcher timed out ###」という内容のファイルが取得できるので、サーバ側で検索のタイムアウトが起きているようです。

meso_cacase @meso_cacase

@windowmoon 検索時間は概ねヒット件数に比例します。エンジンの検索時間、ヒット件数、ウェブの応答時間にそれぞれ上限を設けています。理由は、10万ヒットを超えるような場合はたいていユーザの欲しい結果になっていないうえに、サーバに負荷がかかりすぎるからです。

meso_cacase @meso_cacase

@windowmoon htmlですぐに返ってくるのは50件でヒットの取得を打ち切っているからです。txt等だと10万件まで取得し続けるので時間がかかります。ヒットの件数のみ短時間に返ってきたりすると便利でしょうか（うまく実装できるかわかりませんが）。

windowmoon＠𝕏 @windowmoon

@meso_cacase 全件取得してからローカルで処理することを想定していますから、時間がかかっても全件取得できるようにしていただきたいです。処理の優先度が低い代わりにヒット件数上限を大幅に引き上げたAPIを用意していただけるといいかと。あと、NCBI Taxonomy IDなどで分類群を制限して検索できると最高ですね。

windowmoon＠𝕏 @windowmoon

@meso_cacase ミトゲノム、葉緑体ゲノム、プラスミド、核ゲノムなどで検索範囲を制限する機能とかがあるといいかもしれません(不要な検索とヒットが避けられるので)。ユニバーサルプライマー配列で検索するとヒット件数はどうしても膨大になりますから。

meso_cacase @meso_cacase

@windowmoon 優先度が低いかわりに制限を大幅にゆるめたAPIは、実はヒトゲノムなど一部については用意があります。ただ、DDBJ全体となるとマシンの増強が必要です。マシンを増やさずに対応できるか少し考えましたが、実装にかなり手を入れる必要があり難しいところです。

meso_cacase @meso_cacase

@windowmoon 現状では、おっしゃるように必要な範囲だけを検索対象にしてヒット数を抑制するのが有効だと思います。たとえばプラスミドならDDBJのPATかSYNです。少し古い記事ですがご参考にどうぞ data.dbcls.jp/~meso/meme/arc…

meso_cacase @meso_cacase

@windowmoon 検索範囲については、ご希望があればそのようなDBの追加も検討します。あと、今回のような使い方は想定したことがなかったのですが、今後の改良につながるので参考になります。ありがとうございます。

meso_cacase @meso_cacase

@windowmoon もう一点、RやYなど混合塩基は、全パターン展開してその数だけ検索を繰り返すという手抜き実装で、混合塩基の数が多いと計算時間が爆発的に増えてしまいます（ユーザ側で展開して個々に検索すれば計算時間は変わらずヒット件数を抑制できます）。将来効率化したいです。

windowmoon＠𝕏 @windowmoon

@meso_cacase それは1塩基を4ビットで表現する必要があるんじゃないでしょうか(ギャップも含めるなら5ビット)。全パターン展開は私もPrimer-BLASTにかけるときにやっています。縮重プライマーのアニールする場所を探す需要はあると思うので、是非お願いします。

windowmoon＠𝕏 @windowmoon

@meso_cacase 「検索漏れがない」というのが最大の長所であるにもかかわらず、「ヒットした全件取得ができない」というのは長所を殺してしまっていると思うので、何とか全件取得できるようにしていただきたいところです。今のところ、私はローカルにecoPCRを入れてNCBI ntを対象にin silico PCRしています。