Относительная сложность. Колмогоровский подход

Июль 22, 2022

Главная
Информатика
Относительная сложность. Колмогоровский подход

Содержание

2. Относительная сложность. Обобщение подхода Лемпеля-Зива Представление S1 в виде конкатенации фрагментов из S2 назовем сложностным разложением
3. Относительная сложность и редакционное расстояние S2 = aaaa a cccc c ttttttttttttt – acacacac a atatatat
4. Трансформационное расстояние Трансформационое расстояние и относительная сложность идейно близки. Операция «вставка сегмента» используется, если посимвольная генерация
5. Инверсионное расстояние Инверсионное расстояние dI(π,σ) между последовательностями π и σ определяется минимальным числом инверсий, переводящих одну
6. Точки разрыва π0 = 0 and πN+1 = N + 1 π and σ − произвольные
7. Инверсионное расстояние, число точек разрыва и относительная сложность r(π,σ) ≤ 2dI(π,σ) Точки разрыва однозначно соответствуют границам
8. Phylogenetic trees for 65 species of the genus Chironomus
9. Расстояния и меры сходства, отличные от ред. расстояния Пусть T1 и T2 два текста. Назовем совместной
10. Мера сходства, учитывающая частоты встречаемости подслов: α – произвольная цепочка символов из текстов T1 и/или T2,
11. Ранговые меры близости. Коэффициент корреляции τ
12. Ранговые меры близости. Коэффициент корреляции τ
13. Ранговые меры близости. Коэффициент корреляции τ Пусть l-граммы в Φ l(T1) и Φ l(T2) упорядочены по
14. Ранговые меры близости. Коэффициент Спирмэна
16. Скачать презентацию

Слайд 2

Относительная сложность. Обобщение подхода Лемпеля-Зива
Представление S1 в виде конкатенации фрагментов

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

Слайд 3

Относительная сложность и редакционное расстояние
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
S2 = –––––---tttttttttttttttttaaaaaaaa
S1 = aaaaaaaattttttttttttttttt––---–––
d (S1 , S2) = 16
H(S1 / S2) = aaaaa * ttttttttttttttttt
с (S1 / S2) = 2
c (S1/S2) ≤ 2d(S1, S2) + 1

Слайд 4

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

используется, если посимвольная генерация фрагмента «дешевле» его копирования.
Порядок покрытия 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)

Слайд 5

Инверсионное расстояние
Инверсионное расстояние dI(π,σ) между последовательностями π и σ определяется

минимальным числом инверсий, переводящих одну из них в другую Задача вычисления инверсионного расстояния для перестановок является 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

Слайд 6

Точки разрыва
π0 = 0 and πN+1 = 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.
0 1 2 3 | 8 7 6 | 4 5 | 9 10

Слайд 7

Инверсионное расстояние, число точек разрыва и относительная сложность
r(π,σ) ≤ 2dI(π,σ)
Точки разрыва

однозначно соответствуют границам
компонентов сложностного разложения, построенного с использованием операций прямого и обратного копирования
r(π,σ) = с(π /σ) – 1
σ = 1 2 3 4 5 6 7 8 9
H(π / σ) = 1 2 3 * 8 7 6 * 4 5 * 9
Сложностные разложения позволяют перейти от исходных перестановок к "знаковым" и сократить размерность задачи вычисления инверсионного расстояния

Слайд 8

Phylogenetic trees for 65 species of the genus Chironomus

Слайд 9

Расстояния и меры сходства, отличные от ред. расстояния
Пусть 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)

Слайд 10

Мера сходства, учитывающая частоты встречаемости
подслов:
α – произвольная цепочка

символов из текстов T1 и/или T2,
| α | – ее длина.
(Findler N.V., Van Leeuten, 1979)

Слайд 11

Ранговые меры близости. Коэффициент корреляции τ

Слайд 12

Ранговые меры близости. Коэффициент корреляции τ

Слайд 13

Ранговые меры близости. Коэффициент корреляции τ
Пусть l-граммы в Φ l(T1) и

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

Слайд 14

Относительная сложность. Колмогоровский подход

Содержание

Относительная сложность. Обобщение подхода Лемпеля-Зива Представление S1 в виде конкатенации фрагментов

Относительная сложность и редакционное расстояниеS2 = aaaa a cccc c ttttttttttttt

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

Инверсионное расстояние Инверсионное расстояние dI(π,σ) между последовательностями π и σ определяется

Точки разрыва π0 = 0 and πN+1 = N + 1π

Инверсионное расстояние, число точек разрыва и относительная сложностьr(π,σ) ≤ 2dI(π,σ)Точки разрыва

Phylogenetic trees for 65 species of the genus Chironomus

Расстояния и меры сходства, отличные от ред. расстояния Пусть T1

Мера сходства, учитывающая частоты встречаемости подслов: α – произвольная цепочка

Ранговые меры близости. Коэффициент корреляции τ

Ранговые меры близости. Коэффициент корреляции τ

Ранговые меры близости. Коэффициент корреляции τПусть l-граммы в Φ l(T1) и

Ранговые меры близости. Коэффициент Спирмэна

Похожие презентации

Относительная сложность. Обобщение подхода Лемпеля-Зива
Представление S1 в виде конкатенации фрагментов

Относительная сложность и редакционное расстояние
S2 = aaaa a cccc c ttttttttttttt

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

Инверсионное расстояние
Инверсионное расстояние dI(π,σ) между последовательностями π и σ определяется

Точки разрыва
π0 = 0 and πN+1 = N + 1
π

Инверсионное расстояние, число точек разрыва и относительная сложность
r(π,σ) ≤ 2dI(π,σ)
Точки разрыва

Расстояния и меры сходства, отличные от ред. расстояния
Пусть T1

Мера сходства, учитывающая частоты встречаемости
подслов:
α – произвольная цепочка

Ранговые меры близости. Коэффициент корреляции τ
Пусть l-граммы в Φ l(T1) и