UK 
EnglishТипова
Polski🧬 Найдовша спільна підпослідовність — ДП-вирівнювання
Обчислюйте найдовшу спільну підпослідовність двох рядків через ДП-сітку, тоді простежте діагональні збіги назад — алгоритм за diff-інструментами та порівнянням ДНК-послідовностей.
Про найдовшу спільну підпослідовність
Задача найдовшої спільної підпослідовності (LCS) знаходить найдовшу послідовність символів (не обов'язково неперервну), яка з'являється в однаковому відносному порядку в обох вхідних рядках. Вона розв'язується за O(mn) часу й пам'яті методом динамічного програмування: таблиця L[i][j] зберігає довжину LCS перших i символів рядка A та перших j символів рядка B, з рекурентністю L[i][j] = L[i−1][j−1] + 1, якщо A[i]=B[j], інакше max(L[i−1][j], L[i][j−1]). LCS лежить в основі утиліти diff у Unix, вирівнювання послідовностей ДНК та інструментів виявлення плагіату, де вона визначає максимальну спільну структуру між двома документами чи геномами.
Ця симуляція заповнює таблицю ДП клітинка за клітинкою, а тоді робить зворотний прохід, щоб підсвітити всі оптимальні шляхи вирівнювання через матрицю. Ви також побачите, як LCS пов'язана з відстанню редагування: мінімальна кількість вставок і видалень, потрібних для перетворення A на B, дорівнює (|A| + |B| − 2·LCS(A, B)), що робить ці дві задачі двоїстими поглядами на ту саму базову структуру.
Часті запитання
Яке рекурентне співвідношення для LCS?
L[i][j] = 0, якщо i=0 або j=0 (базовий випадок порожнього рядка); L[i][j] = L[i−1][j−1] + 1, якщо A[i] = B[j] (символи збігаються, подовжуємо LCS); L[i][j] = max(L[i−1][j], L[i][j−1]) в іншому випадку (беремо краще з пропуску одного символу з будь-якого рядка). Зворотний прохід від L[m][n], що йде по діагоналі (збіг) і напрямку максимуму, відновлює саму послідовність LCS.
Чи є LCS єдиною?
Ні — може існувати кілька LCS однакової максимальної довжини. Наприклад, LCS("ABCB", "BDCAB") має довжину 3, причому і "BCB", і "BCA" — обидві дійсні найдовші спільні підпослідовності. У найгіршому випадку кількість різних LCS може бути експоненційною відносно довжин рядків. Зворотний прохід таблицею ДП може дати будь-яку з них; для перерахування всіх потрібен додатковий облік.
Як LCS пов'язана з відстанню редагування?
Якщо дозволені лише вставки й видалення (без замін), відстань редагування(A, B) = |A| + |B| − 2·LCS(A, B). Кожен збіжний символ у LCS уникає одного видалення й однієї вставки, заощаджуючи 2 операції. Відстань Левенштейна додає заміни як опціональне скорочення (вартість 1 замість видалення+вставки = вартість 2). Обидві таблиці ДП структурно ідентичні, відрізняючись лише способом обчислення діагональної клітинки (незбіг).
Що таке алгоритм Ханта–Шиманського для розрідженої LCS?
Для послідовностей із малою кількістю пар збігів (розріджений набір збігів) алгоритм Ханта–Шиманського знаходить LCS за O((r + n) log n), де r — кількість позицій-збігів. Спочатку він перераховує всі пари (i, j), де A[i]=B[j], а тоді знаходить найдовший зростаючий ланцюг цих пар за y-координатою — що еквівалентно задачі найдовшої зростаючої підпослідовності. Це значно швидше за O(mn), коли алфавіт великий або послідовності мають мало спільних символів.
Чи можна обчислити LCS швидше, ніж за O(mn)?
Для довільних послідовностей над довільним алфавітом найкращі відомі алгоритми працюють за O(mn/log n) із застосуванням паралелізму на рівні слів (бітово-векторні методи). Для малих алфавітів метод «чотирьох росіян» досягає O(mn/log2 n). Для випадкових рядків над алфавітом розміру k очікувана довжина LCS приблизно дорівнює γ·n, де γ залежить від k (наприклад, γ ≈ 0,8 для бінарного алфавіту), і алгоритми, що використовують цю структуру, можуть бути швидшими на практиці.
Як команда Unix diff використовує LCS?
Unix diff обчислює LCS двох файлів, розглянутих як послідовності рядків. Рядки в LCS вважаються «незміненими»; рядки у файлі A, яких немає в LCS, — «видаленими» (позначені −); рядки у файлі B, яких немає в LCS, — «доданими» (позначені +). Результатом є мінімальний сценарій редагування для перетворення одного файлу на інший. Алгоритм diff у Git (patience diff, histogram diff) використовує варіанти LCS з евристиками для отримання більш читабельних для людини порівнянь типового вихідного коду.
Що таке задача найдовшого спільного підрядка і чим вона відрізняється від LCS?
Найдовший спільний підрядок (не підпослідовність) вимагає, щоб символи-збіги були неперервними в обох рядках. Вона розв'язується за O(mn) часу з таблицею ДП, де L[i][j] = L[i−1][j−1]+1, якщо A[i]=B[j], інакше 0, а відповідь — max(L[i][j]). Ефективніше узагальнене суфіксне дерево розв'язує її за O(m+n). LCS ≥ довжина найдовшого спільного підрядка загалом, оскільки підпослідовності гнучкіші.
Як LCS застосовується в біоінформатиці?
У вирівнюванні послідовностей ДНК чи білків LCS визначає консервативні ділянки між двома геномами або білковими послідовностями. Алгоритм Нідлмана–Вунша (глобальне вирівнювання) математично еквівалентний LCS із настроюваними оцінками збігів і штрафами за пропуски. Виявлення LCS-подібних консервативних доменів між геномами людини й миші розкриває функціонально важливі ділянки під еволюційним тиском, спрямовуючи анотацію генів і пошук мішеней для ліків.
Який зв'язок між LCS і найдовшою зростаючою підпослідовністю?
LCS можна звести до задачі найдовшої зростаючої підпослідовності (LIS): замінити кожен символ у A його рангом серед збігів у B, а тоді знайти LIS отриманої послідовності позицій. І навпаки, LIS можна розв'язати за O(n log n) за допомогою пасьянсного сортування. Алгоритм розрідженої LCS Ханта–Шиманського використовує саме це зведення, даючи O(r log n) для розріджених наборів збігів, де r — кількість пар-збігів.
Скільки пам'яті потребує LCS і чи можна її зменшити?
Стандартне ДП використовує O(mn) пам'яті для повної таблиці. Алгоритм Гіршберга (1975) обчислює LCS за O(mn) часу, але лише за O(min(m,n)) пам'яті, використовуючи метод «розділяй і володарюй»: він розбиває задачу в середньому рядку, знаходить, де оптимальний шлях LCS перетинає цей рядок, використовуючи лінійну пам'ять, а тоді рекурсивно обробляє обидві половини. Це та сама техніка, що використовується для просторово-ефективного вирівнювання послідовностей у біоінформатиці.