Самая длинная подстрока (для последовательностей триплетов)

Question

Я пытаюсь сравнить строки в формате: AAA-ABC-LAP-ASZ-ASK; в основном, тройки букв, разделенных черточками.

Я пытаюсь найти между 2 такими последовательностями произвольной длины (от 1 до 30 триплетов) самую длинную последовательность общих триплетов.

Например, AAA-BBB-CCC-AAA-DDD-EEE-BBB и BBB-AAA-DDD-EEE-BBB можно найти последовательность из 5 (BBB-AAA-DDD-EEE-BBB, даже если CCC отсутствует во 2-й последовательности).

Черточки не следует рассматривать для сравнения; они служат только для разделения триплетов.

Я использую Python, но просто общий алгоритм для достижения этой цели должен:)

Answer 1

Я думаю, что вы ищете алгоритм Longest Common Subsequence , который может найти эту последовательность очень быстро (за O (n ² ) времени). Алгоритм основан на простом повторении динамического программирования, и есть много примеров того, как вы могли бы реализовать алгоритм.

Интуитивно, алгоритм работает, используя следующую рекурсивную декомпозицию, которая работает, просматривая первый триплет каждой последовательности:

• Если любая последовательность пуста, самая длинная общая подпоследовательность - пустая последовательность.
• В противном случае:
  • Если первые триплеты каждой последовательности совпадают, то LCS - это тот элемент, за которым следует LCS остатков двух последовательностей.
  • Если нет, LCS является более длинным из следующих: LCS первой последовательности и все, кроме первого элемента второй последовательности, или LCS второй последовательности и все, кроме первого элемента первой последовательности.

Надеюсь, это поможет!

Answer 2

Выравнивание последовательностей алгоритмы, которые обычно используются в биоинформатике, могут быть использованы здесь.Они в основном используются для выравнивания односимвольных последовательностей, но они могут быть изменены, чтобы принимать n-символьные последовательности. Алгоритм Нидлмана – Вунша является довольно эффективным.

Answer 3

Для начала вы можете, по крайней мере, уменьшить проблему, рассчитав установить симметричную разность , чтобы исключить любые триплеты, которые не встречаются в обеих последовательностях.

Для самой длинной подпоследовательностиАлгоритм использует динамическое программирование подход.Для каждого триплета найдите самую короткую подстроку длины два, которая встречается в обоих.Цикл по этим парам, пытаясь расширить их путем объединения пар.Продолжайте расширяться, пока у вас не будет всех самых длинных расширений для каждого триплета.Выберите самый длинный из них:

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.