Презентация на тему Максимально длинная общая подпоследовательность (МДП, LCS)

0) = 0;
0 ≤ i ≤ m;

0 ≤ j ≤ n;

Пример. А = aacacbb; B = ababc. L(A,B) = 3.
Всего 13 МДП:
3 – abb,
6 – aab,
4 – aac

j) – длина МДП текстов А[i + 1 :

m] и B[j + 1 : n].
Тогда для любого i: L(m,n) = maxj{L(i, j) + L*(i, j)}

– наим. j, такое что (L(A[1 : i], B[1

: j]) = k

Начальные условия:
Qi,0 = 0, 0 ≤ i ≤ n;
Q0k = n + 1, 1 ≤ k ≤ min(m,n);
Пример. А = aacacbbс,
B = ababc.
Трудоемкость: O(r × log n),

где

число потенциально возможных парных соответствий символов

j, такое что (L(A[i : m], B[j : n])

= k

Начальные условия:
Ri,0 = n + 1, 0 ≤ i ≤ m;
Rm + 2 – k, k = 0, 1 ≤ k ≤ min(m,n);
Пример. А = aacacbb,
B = ababc.
Трудоемкость: O(n× (m – L)),

merging): построение текста Т3, сумма переходов к которому от

Т1 и Т2 минимальная. В зависимости от весов ред. операция в качестве Т3 можно получить МДП, наименьшую надпоследовательность, один из текстов (Т1 или Т2), наиболее вероятного предка и т.п.

поиск максимально длинной общей подпоследовательности для группы текстов.

задача о максимально длинной возрастающей (убывающей) подпоследовательности для числовой перестановки

расстояния
Пусть T1 и T2 два текста.
Назовем совместной

частотной характеристикой l-го порядка
текстов T1 и T2 совокупность элементов
Φ l (T1, T2)= {φ l1(T1, T2), φ l2(T1, T2), …, φ l Ml (T1, T2)}
где Ml = Ml (T1, T2) — число l-грамм, общих для обоих текстов,
а элемент φ l i (1 ≤ i ≤ Ml) есть тройка:
<< i-я общая l-грамма – xi,
частота ее встречаемости в T1 – F(T1, xi) и в T2 – F(T2, xi) >>.
Простейший набор мер сходства, упорядоченный по возрастанию l
имеет вид:
,

l = 1,2,…,lmax(T1,T2)

α – произвольная цепочка текстов T1 и (или) T2,

| α | – ее длина.
(Findler N.V., Van Leeuten, 1979)

Φ l(T1) и Φ l(T2) упорядочены по убыванию частот.

Порядковое место l-граммы xi в упорядочении определяет ее ранг –
r(T1 , xi) (соответственно, r(T2 , xi)).

Φ l(T1) и Φ l(T2) упорядочены по убыванию частот;

порядковое место l-граммы xi в упорядочении определяет ее ранг –
r(T1 , xi) (соответственно, r(T2 , xi)).
Группы равночастотных l-грамм представляются усредненным рангом.
Введем l-граммный аналог расстояния:



где Σl – совокупность всевозможных цепочек длины l ; | Σl | = Rl = nl.
Аналогом коэффициента Спирмэна для характеристики l-го порядка
(l = 1,2,…) является

(**)

При наличии равночастотных l-грамм в (**) вносится поправка на "связанность" рангов. (Кендел М. Ранговые корреляции, М., Статистика, 1975)

для сравнения m последовательностей.

Вычисляем суммы рангов каждого объекта

Среднее значение суммы рангов одного объекта составляет ES = m(n+1)/2.

S – сумма квадратов отклонений от ES



Равночастотным l-граммам назначаются усредненные ранги и в определения τ, ρ, W вносится поправка на "связанность".
t – число элементов в одной группе.

W, в отличие от τ и ρ изменяется от 0 до 1.

фрагментов из S2 назовем сложностным разложением S1 по S2.

На каждом шаге копируется максимальный фрагмент S2, совпадающий с префиксом непокрытого участка S1
Если такого фрагмента нет, используется операция генерации символа
c(S1 / S2) – сложность S1 относительно S2 определяется числом компонентов в разложении S1 по S2

= aaaa a cccc c ttttttttttttt – acacacac

a atatatat
S1 = aaaa g cccc g ttttttttttttt g acacacac g atatatat
d(S1,S2) = 4
H(S1/S2) = aaaa*g*cccc*g*ttttttttttttt*g*acacacac*g*atatatat
c(S1/S2) = 9

c (S1/S2) ≤ 2d(S1, S2) + 1

S2 = –––––---tttttttttttttttttaaaaaaaa
S1 = aaaaaaaattttttttttttttttt––---–––

d (S1 , S2) = 16

H(S1 / S2) = aaaaa * ttttttttttttttttt
с (S1 / S2) = 2

близки.
Операция «вставка сегмента» используется, если посимвольная генерация фрагмента «дешевле»

его копирования.
Порядок покрытия S1 предполагает оптимизацию по всем парам межтекстовых повторов и промежуткам между ними. O(N6).
J.-S.Varré, J.-P.Delahaye, E. Rivals: Transformation Distances: a Family of Dissimilarity Measures Based on Movements of Segments. // Bioinformatics 15(3): 194-202 (1999)

и σ определяется минимальным числом инверсий, переводящих одну из

них в другую Задача вычисления инверсионного расстояния для перестановок является NP-полной
В случае "знаковых" перестановок существуют полиномиальные решения
+1 [+2 −4 −5 ] +3 +6 → +1 +5 +4 −2 +3 +6

Hannenhalli, S. and Pevzner, P. Transforming Cabbage into Turnip (Polynomial Algorithm for Sorting Signed Permutation by Reversals). Proc. 27th Ann. ACM Symposium on the Theory of Computing, 1995, pp. 178–189

N + 1
π and σ − произвольные перестановки.
Разрыв между

πi = a и πi+1 = b фиксируется, если в σ нет биграмм ab и ba.
π = 0 | 6 4 | 1 8 5 | 3 | 2 9 7 | 10 r(π, σ) = 5
σ = 0 | 5 8 1 | 2 9 7 | 6 4 | 3 | 10

σ − тождественная перестановка (1 2 … N).
Число точек разрывов (breakpoint distance) r(π, σ) определяется количеством позиций π таких что | πi − πi+1| ≠ 1.
1 2 3 | 8 7 6 | 4 5 | 9