最長の部分文字列（トリプレットのシーケンスの場合）

Question

フォーマットの文字列を比較しようとしています：AAA-ABC-LAP-ASZ-ASK;基本的に、三つの文字がダッシュで区切られています。

私は一般的なトリプレットの最長のシーケンスを任意の長さ（1から30トリプレット）の2つのそのようなシーケンスの間で見つけることを試みています。

たとえば、AAA-BBB-CCC-AAA-DDD-EEE-BBBおよびBBB-AAA-DDD-EEE-BBBでは、5つのシーケンス（BBB-AAA-DDD-EEE-BBB、even CCCが第2の配列に存在しない場合）。

比較のためにダッシュを考慮しないでください。彼らは三つ子を分ける役目しか果たしません。

私は、Pythonを使用していますが、これを達成するために、単に一般的なアルゴリズムが何をすべき:)

Answer 1

をスタートとして、あなたは、少なくとも両方で発生していない任意のトリプレットを排除するためにset symmetric differenceを計算することによって、問題を軽減することができますシーケンス。

最長のサブシーケンスでは、アルゴリズムはdynamic programmingアプローチを使用します。それぞれのトリプレットについて、長さ2の最短部分文字列を両方の文字列で見つけます。これらのペアをループし、ペアを結合してそれらを拡張しようとします。各トリプレットの長さが最も長くなるまで拡張してください。これらの最長選ん：一般的に、バイオインフォマティクスに使用されている

ABQACBBA 
ZBABBA 

Eliminate symmetric difference 
ABABBA and BABBA 


Start with the first A in ABABBA. 
It is followed by B, giving the elements [0,1] 
Check to see if AB is in BABBA, and record a match at [1,2] 
So, the first pair is ((0,1), (1,2)) 

Next, try the first B in ABABBA. 
It is followed by an A giving the elements [1,2] 
Check to see if BA is in BABBA and record a match at [0,1] 

Continue with the rest of the letters in ABABBA. 

Then, try extensions. 

The first pair AB at [0,1] and [1,2] can be extended from BA 
to ABA [0,1,3] and [1,2,4]. Note, the latter group is all the 
way to the right so it cannot be extended farther. ABA cannot 
be extended. 

Continue until all sequences have extended are far as possible. 
Keep only the best of those. 

Answer 2

Sequence alignmentアルゴリズムを、ここで使用することができます。それらは主に1文字シーケンスの整列に使用されますが、n文字シーケンスを受け入れるように変更できます。 Needleman–Wunsch algorithmはかなり効率的です。

Answer 3

Longest Common Subsequenceアルゴリズムを探していますが、これは非常に迅速にこのシーケンスを見つけることができます（O（n ）時）。このアルゴリズムは、単純な動的プログラミングの再帰に基づいており、アルゴリズムをどのように実装するかについてオンラインで多くの例があります。最長共通部分列が空のシーケンスである、

• いずれかの配列が空の場合：

  直感的に、アルゴリズムは、各シーケンスの最初のトリプレットを見て、働く、次の再帰的な分解を使用して動作します。

• その他：
  • 各シーケンスの最初のトリプレットが一致する場合、LCSはその要素であり、2つのシーケンスの残りの部分のLCSが続きます。
  • LCSは、最初のシーケンスのLCSと2番目のシーケンスの最初の要素以外のLCS、または2番目のシーケンスのLCSと1番目のシーケンスの最初の要素を除くすべてのLCSのうち、長いものです。