4

OKこれは私がやりたいことです:

2 つ以上の文字列を取得し、それらを「整列」します (DNA/RNA シーケンスなどはなく、それぞれに 1000 個ほどのアイテムがない通常の文字列のみ)。

ペアワイズ アラインメント (2 つの文字列をアラインする) については既にいくつかの作業を行っていますが、複数のペアをアラインしようとすると、「ギャップ」が問題を引き起こします。

例（私が現在テストしているもの）：

ABCDEF
ABGHCEEF
AJKLBCDYEOF

AB--CDEF
ABGHCEEF
=======================
AB--C-EF

A-B--C--E-F
AJKLBCDYEOF
=======================
A----C--E-F

そして別の（より説明的な）例：

http://nest.drkameleon.com
http://www.google.com
http://www.yahoo.com

http://nest.drkameleon.com
http://-www.--google--.com

=======================
http://----.------le--.com

http://----.------le--.com
http://-www.-----yahoo.com

=======================
http://----.----------.com

私が現在していること：

  • 文字列を並べ替える (長い文字列がリストの最初に来る)
  • 最初のペア : AB を整列させ、結果を取得します (たとえばR1)
  • 次に、2 番目のペア :R1とC(結果はR2)を揃えます。
  • 次に、3 番目のペアR2を揃えます。D
  • 等々...

それで、あなたの心の中には何がありますか？どうすればそれを手に入れることができますか？より良い方法はありますか？（もちろんあるはず…）

私はPerl/Pythonまたはこれらの行に沿った何かでそれを行いたいと思っていますが、あらゆるタイプのコード/リファレンスは大歓迎です! :-)

4

2 に答える 2

1

この問題を、文字列の配置ではなく、より一般的な文字列の差分の問題としてキャストできると思います。2 つのファイルの違いを見つけるためにGNU がどのように使用されるかを検討し、N-way を実行するために使用されるのと同じアルゴリズムを使用します。diffdiff

このアプローチの時間/メモリの複雑さがニーズに適しているかどうかはわかりませんが、少なくともこの方法で問題を考えることができます。

于 2012-04-09T13:18:19.577 に答える
1

オプションのスペースを使用して、最長の共通シーケンスを計算するレーベンシュタイン アルゴリズムに基づくアルゴリズムがあります。それが役立つかどうかはわかりません。

于 2012-04-09T15:46:38.963 に答える