複数シーケンスアラインメント（最長共通部分シーケンス）？

OK、これは私が何をしたいです：複数シーケンスアラインメント（最長共通部分シーケンス）？

以上の2つの文字列を取得し、それらを「合わせる」（無DNA/RNA配列またはそれらの各1000個のアイテムのようではないとのような、普通の文字列）

私は既にペアワイズアラインメント（2つのストリングのアライメント）を行ってきましたが、2つ以上のペアをアライメントしようとすると「ギャップ」が私にいくつかの問題を引き起こします。

例（1私は現在テストしています）：

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を言わせて）：R1とC（R2の結果を） R2とD
のように...

だからあなたの心の中で何：

は、次に第三のペアを揃えますか？どうすればそれに行くことができますか？より良い方法がありますか？（もちろん、あります...）

私はむしろPerl/Pythonやこれらの行に沿って何かをしたいと思いますが、どのような種類のコード/リファレンスも歓迎すべきものです！ :-)

出典

2012-04-09 Dr.Kameleon

おそらく入力と出力の例をいくつか投稿できますか？私はあなたが実際にやりたいことに100％ではありません。 –

も、PythonのLCS問題を詳細に説明するこの記事を見てください。 http://wordaligned.org/articles/longest-common-subsequence#toc21 – luke14free

@リチウムaungYipは、ここで私が何を意味するかです：http://stackoverflow.com/questions/10065293/how-to-align-2-strings –

私はあなたの代わりに文字列アライメントのより一般的な文字列デフ問題としてこの問題をキャストすることができるかもしれないと思います。 GNU diffが2つのファイル間の相違点を見つけるためにどのように使用されているかを検討し、N-way diffを実行するのと同じアルゴリズムを使用してください。

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

出典

2012-04-09 13:18:19

「diff」がこの場合にどのように役立つのか正確にはわかりません... –

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

出典

2012-04-09 15:46:38 Alberto

Levenshteinアルゴリズムを多用していて、Hirschbergにも試してみましたが、 ** Needleman-Wunschアルゴリズム**（http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm） –

複数シーケンスアラインメント（最長共通部分シーケンス）？

答えて

関連する問題