多重配列アラインメントについてです。


情報科学を専攻しているものです。
最近ひょんなことから多重配列アラインメント(multiple sequence alignment)の研究をすることになったのですが、
バイオ系のことをさっぱり知らないので、どんなデータに対して、どういう評価値に基づいて
実験、解析を行えばいいのかがさっぱりわかりません。
とりあえず線形的なコストの最適化問題として解こうとは思っているのですが。。。

そこで、多重配列アラインメントを実験するときにはどのようなデータに対して、
どのように実験すればいいのかが分かる情報があれば教えていただきたいです。
この分野の教科書か、先行研究のサーベイなんかもあれば教えていただけると助かります。

回答の条件
  • 1人3回まで
  • 13歳以上
  • 登録:2010/02/21 08:14:15
  • 終了:2010/02/27 13:11:47

ベストアンサー

id:TAK_TAK No.2

tak回答回数988ベストアンサー獲得回数822010/02/21 10:31:35

ポイント50pt

ClustalW

たぶん後で実際に実験することになるので、

local-multiple-alignmentのアルゴリズムを実際に見てみるべきです。

バイオ系のことをさっぱり知らないので

多重配列アラインメントの研究をするだけ、であるとするなら

対象はバイオインフォマティクスには限らないのですが

こう言っている以上、多分そのようなことをやるのだと思います。



どのようなデータに対して、どのように実験すればいいのか

様々な人が様々なデータに対して先行研究を行って実験用コーパスもたくさん作られていたので、その中には自由に使用できるコーパスがあったはずです。

local multiple alignment corpus

id:kabisuke

詳しい回答ありがとうございます。

すみません、説明不足でした。

「多重配列アラインメント」という問題自体に興味があって行うので、

バイオインフォマティクスに限るつもりではないのですが、

実験にあたっては実用上のインパクトを考えて研究者で

良く用いられるコーパスを用いた方が良いのではないかと考えています。

このClustalWというのは実際にアラインメントをつくってくれるツール(?)みたいですね。

この業界では評価関数でよく用いられるものというのがあるんでしょうか。

見た感じヒューリスティックで近似解を求めているように見えますが。。。

(まずは厳密アルゴリズムから考えてみたいと思っていたのですが)

2010/02/21 13:16:48

その他の回答(1件)

id:km1967 No.1

km1967回答回数541ベストアンサー獲得回数402010/02/21 09:40:16

ポイント20pt

バイオインフォマティクス基礎講義―一歩進んだ発想をみがくために

バイオインフォマティクス基礎講義―一歩進んだ発想をみがくために

  • 作者: アーサー・M. レスク
  • 出版社/メーカー: メディカルサイエンスインターナショナル
  • メディア: 単行本

id:kabisuke

わかりやすそうですね。探してみることにします。ありがとうございます。

2010/02/21 13:04:54
id:TAK_TAK No.2

tak回答回数988ベストアンサー獲得回数822010/02/21 10:31:35ここでベストアンサー

ポイント50pt

ClustalW

たぶん後で実際に実験することになるので、

local-multiple-alignmentのアルゴリズムを実際に見てみるべきです。

バイオ系のことをさっぱり知らないので

多重配列アラインメントの研究をするだけ、であるとするなら

対象はバイオインフォマティクスには限らないのですが

こう言っている以上、多分そのようなことをやるのだと思います。



どのようなデータに対して、どのように実験すればいいのか

様々な人が様々なデータに対して先行研究を行って実験用コーパスもたくさん作られていたので、その中には自由に使用できるコーパスがあったはずです。

local multiple alignment corpus

id:kabisuke

詳しい回答ありがとうございます。

すみません、説明不足でした。

「多重配列アラインメント」という問題自体に興味があって行うので、

バイオインフォマティクスに限るつもりではないのですが、

実験にあたっては実用上のインパクトを考えて研究者で

良く用いられるコーパスを用いた方が良いのではないかと考えています。

このClustalWというのは実際にアラインメントをつくってくれるツール(?)みたいですね。

この業界では評価関数でよく用いられるものというのがあるんでしょうか。

見た感じヒューリスティックで近似解を求めているように見えますが。。。

(まずは厳密アルゴリズムから考えてみたいと思っていたのですが)

2010/02/21 13:16:48
  • id:TAK_TAK
    ClustalWで近似解を求める...というか、この手の問題では厳密解を求めることは計算量的に非常に困難です。
    しかし必ずしもヒューリスティック?とは言えないと思ってるんですが...






    ところで、
    multiple-alignmentだけが対象なのでしょうか?
    local-alignemntの方は全く考えなくてもよいのでしょうか?

    だとすると、問題の難易度はだいぶ下がると思うのですが...
  • id:kabisuke
    出力解に対してあるコスト関数が与えられて、それに対する最大化、最小化を考えるなら
    一応最適化問題で、その最適解に対して出力解のコストの保証ができないなら
    ヒューリスティックスと呼んで差し支えない気がします。
    (これは計算科学的な考え方なんですけど)

    計算量的に困難だ、というのは配列の本数をm、各長さがlで一様だとしたらO(l^m)くらいの
    計算時間がかかるのが普通、ということですよね。(動的計画法ならそれくらいのはず?)
    とりあえず、ではあるのですがmを最大でも5くらいに抑えた上で計算してみたいと思っています。
    興味は空間計算量をどのレベルまで抑えて厳密解が出せるのかというところにもあります。
    スパコンで並列計算すれば、時間をかければm=5くらいなら計算できるんじゃないかと踏んでるんですが。
    勿論配列の長さにも依存するので、研究の対象としてどれくらいの大きさの配列を
    扱えば「まともな結果」となるか、を知りたいという理由でもこの質問を書きました。

    local-alignmentは勉強不足で知りませんでした。globalでなくちゃいけない理由は全くないです。
    ただ、計算時間または出力解を解析できるアルゴリズムの設計をしたいと思っているので、
    localの場合の現状がどうなっているのかは知りたいところです。
    ご存知でしたら是非お願いいたします。

  • id:TAK_TAK
    計算科学的なスタンスで厳密解を求めるためにアルゴリズムの設計をする....
    のであれば、既存の研究はほとんど関係ない純粋な数学的な問題になると思います。




    厳密解とか、評価関数とか、「まともな結果」とか、
    「正解」があるという前提に立っているようなので、
    でしたら、

    そういう理想的な問題設定をするということが正しい方法だと思います



    (バイオインフォマティクスとか)実世界の問題に対して高速で近似解が求められれば十分な...
    というか、正解がそもそも存在するかしないかが分からないのでalignmentをやっている問題とは、かけ離れた 
    理想的すぎる問題を扱いたいようなので

  • id:kabisuke
    うーん、伝わりにくいコメントを書いてしまって申し訳ないです。
    「正解」があるのが前提だと考えているわけではないのですが。。。

    既存の研究に対して新しいアルゴリズムを提案したら、
    当然「何らかの観点」でそのアルゴリズムは評価されますよね?
    おそらくその観点は、感覚的には
    「それっぽいアラインメントである」とか
    「結構速く動く」とか、
    そんな感じのものなんではないかと思います。

    ですが、研究である以上は「それっぽい」じゃ自己満足でしかないですよね?
    多分ですが「それっぽさ」は何かしら定義があるはずです。
    (それともそれは生物学者さんの「勘」でしか測れない世界なんですか?
    だとしたら私が研究する余地はどこにもないので、諦めてこの分野から立ち去りますが。。。)

    つまり、どんなアラインメントが得られれば「良い」としているのか、という概念自体はあるはずです。
    それを「評価関数」と呼ぶのではないでしょうか。

    だからある単一な「正解」のみに対してアプローチするのでなく、
    様々な「良い」の概念に対して計算を考えるのがよいはずだ、と考えています。
    ただ、取っかかりとして多くの生物学者さんが「良い」と思うのは
    どのような基準に基づくのか、それが知りたいというわけです。



    ちなみに「まともな結果」という言葉の意味は「何が調べられたら実際に使えるんだろう」という意味です。
    例えば、いくら理論がしっかりしていても、シーケンスの長さが100以上じゃまともに動かないよ、
    というアルゴリズムを提案したって「使えない」で一蹴されてしまうわけで。
    現場ではどのレベルのモノが求められるのかが知りたい、という意味です。
    決して「理想化した純粋数学」の問題として知りたい、という意味でなく
    むしろ「現実ではどうなのか」が知りたい、という意味です。わかりにくくてすみません。
  • id:TAK_TAK
    「何が調べられたら実際に使えるんだろう」ということであれば、


    本数:m
    長さ:l

    だったら、
    m>10^x
    l>10^y

    ぐらいのスケールは当然要求します。
    これを現実的な時間内に解く




    評価の観点としては、
    実行時間は大きいです。
  • id:TAK_TAK
    「それっぽさ」は、生物学者さん...というより各研究者の「勘」でしか測れない世界だと思います。

    自分が得たいalignmentを作るために距離関数やアルゴリズムを工夫するのです。(というアプローチがあります)
    ですので、alignmentの良し悪しはその人が勝手に評価関数を設定します(設定するほうが少ないと思いますが)

    それが「それっぽさ」です。
    「それっぽさ」を合理化するために様々な根拠を提示するのだと思います。





    どんなアラインメントが得られれば「良い」としているのか、
    どのような基準に基づくのか、という共通の概念は

    似ている領域がそろっていること

    です。たぶんこれだけです

    同じ結果に対して似ている似ていない、そろってるそろってないと評価が分かれると思いますが.....

    「似ている」をどう定義したのか
    「そろっている」をどう定義したのか、は、個別の研究事例によってバラバラだと思います。
    そういう結果が出るようにアラインメントを定義したのだから
    このアラインメントではこの結果が必然(正解)である。と主張すると思います。




  • id:kabisuke
    揚げ足をとりたいわけではないのですが
    m>10^x
    l>10^y
    というのは何も言ってないに等しいですよね。xとyが何なのかわからないですから。
    たとえx、yが1以上としても、こんどは「ゲノムの長さと同じ本数のゲノムを用意して比べる」
    っていう意味になっちゃうんでそれはどんなアルゴリズムを用いたって終わらないことでしょう。

    ですが、なんとなくTAK_TAKさんの主張がわかってきました。
    多重配列アラインメントはあまりに計算量が大きくて、
    しかも「それっぽさ」が定義しにくい難儀な分野なんですね。

    情報科学でも似たような分野の問題がありますね。
    クラスタリングアルゴリズムとかは様々な手法が提案されていて、
    きちんと目標関数をあたえて、それのヒューリスティックを求める場合や、
    関係が近いものをどん欲に集めていって完成させてしまうものなど、様々です。
    それぞれの結果を「よい」とする統一的な概念は「あまり」ありません。
    (エントロピーとかを使うと統一的に見ることができますけど、
    エントロピーの値が高いか低いかだけで結果の面白さを測ることはできないです)


    で、結局よくわからなくなってきたので教科書を探しました。

    http://www.amazon.co.jp/%E3%83%90%E3%82%A4%E3%82%AA%E3%82%A4%E3%83%B3%E3%83%95%E3%82%A9%E3%83%9E%E3%83%86%E3%82%A3%E3%82%AF%E3%82%B9%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%85%A5%E9%96%80-Pavel-Pevzner/dp/4320056507

    この本はかなり良書だと感じました。(情報科学やっている人から見ると)
    生物学的なアプローチと情報科学的なアプローチの両面が書かれていてとっつきやすいです。
    各種問題はきちんと定式化されているのでクリアですし。

    ClustlWなどで用いている累進法も概要は理解できました。
    発想は階層的に近いところからペアワイズで組み合わせていくんですね。
    階層型クラスタリングの発想に非常に近いところにあると思いました。
    そういう意味でもTAK_TAKさんがおっしゃることがよくわかりました。

    ただその一方で、やはり「ペアワイズのスコアをマルチプルにそのまま適用は難しい」
    からやったのだ、という発想のプロセスもやはりあるようで、
    私のような厳密からどう緩和すると現実に追いつくか、というアプローチも十分実用的である、
    という風にも感じました。

    まぁ斜め読みしただけの感想なので語弊があるかもしれません。
    何か思うところ、ご指摘あれば是非ご鞭撻お願いします。



  • id:TAK_TAK
    そこまで考えているんだったら
    kabisuke さんが疑問に思っていることを解くために研究するべきです



    というコメントを書いたと思ったのですが
    書けていませんでした


    がんばって研究してください
  • id:kabisuke
    期限ですので打ち切らせていただきました。
    長らく議論につきあっていただいたTAK_TAKさんにいるか賞を差し上げます。

    この分野を追ってこの質問にたどり着いた方のために、もう一つ参考になった教科書を。

    バイオインフォマティクス ゲノム配列から機能解析へ 第2版 (大型本)
    http://www.amazon.co.jp/%E3%83%90%E3%82%A4%E3%82%AA%E3%82%A4%E3%83%B3%E3%83%95%E3%82%A9%E3%83%9E%E3%83%86%E3%82%A3%E3%82%AF%E3%82%B9-%E3%82%B2%E3%83%8E%E3%83%A0%E9%85%8D%E5%88%97%E3%81%8B%E3%82%89%E6%A9%9F%E8%83%BD%E8%A7%A3%E6%9E%90%E3%81%B8-%E7%AC%AC2%E7%89%88-%E3%83%9E%E3%82%A6%E3%83%B3%E3%83%88-%E3%83%87%E3%83%BC%E3%83%93%E3%83%83%E3%83%89/dp/4895924262

    一万以上する大型本ですので研究室にでも買ってもらってください(笑)
    この分野の総ざらいができます。
    各章のはじめに「生物医学系の人のために」「情報系の人のために」というコーナーが
    それぞれもうけてあって、両者にとって有意なイントロダクションになってます。
    まぁ分厚くてまだ全然読めてませんが。

    バイオインフォマティクスはまだまだ研究の余地がありそうで、
    情報科学の人間としてもおもしろそうですね。
    これからじっくり研究してみます。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません