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

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






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

だとすると、問題の難易度はだいぶ下がると思うのですが...

出力解に対してあるコスト関数が与えられて、それに対する最大化、最小化を考えるなら
一応最適化問題で、その最適解に対して出力解のコストの保証ができないなら
ヒューリスティックスと呼んで差し支えない気がします。
（これは計算科学的な考え方なんですけど）

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

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

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




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

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



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

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

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

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

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

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



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

「何が調べられたら実際に使えるんだろう」ということであれば、


本数：m
長さ：l

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

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




評価の観点としては、
実行時間は大きいです。

「それっぽさ」は、生物学者さん...というより各研究者の「勘」でしか測れない世界だと思います。

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

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





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

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

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

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

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

揚げ足をとりたいわけではないのですが
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さんがおっしゃることがよくわかりました。

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

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

そこまで考えているんだったら
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

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

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