7.3: Динамічне програмування

Last updated
Save as PDF

Page ID: 66645

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Дві послідовності розумних розмірів не можуть бути вирівняні грубою силою. На щастя, існує ще один алгоритм, запозичений з інформатики, динамічне програмування, який використовує динамічну матрицю.

Що потрібно, так це скорингова система, щоб судити про якість вирівнювання. Мета полягає в тому, щоб знайти розклад, який має максимальний бал. Припускаємо, що вирівнювання символу$a_{i}$ з символом$b_{j}$ має оцінку$S\left(a_{i}, b_{j}\right) .$ Наприклад, при вирівнюванні двох послідовностей ДНК може бути оцінений як збіг (A-A, C-C, T-T, G-G)$+2$, так і невідповідність$(\mathrm{A}-\mathrm{C}, \mathrm{A}-\mathrm{T}, \mathrm{A}-\mathrm{G}$ і т.д. $)$забив як$-1$. Ми також припускаємо, що індель (нуклеотид, вирівняний з проміжком) оцінюється як$g$, з типовим значенням для вирівнювання ДНК$g=-2$. У наступному розділі ми розробляємо більш якісну та більш широко використовувану модель скорингу інделів, яка відрізняє отвори зазорів від розширень зазорів.

Тепер, давайте$T(i, j)$ позначимо максимальну оцінку для вирівнювання послідовності довжини$i$ з послідовністю довжини$j .$ Ми можемо обчислити за$T(i, j)$ умови, що ми знаємо$T(i-$$1, j-1), T(i-1, j)$ і$T(i, j-1)$. Дійсно, наша логіка схожа на ту, що використовується при підрахунку загальної кількості вирівнювань. Є знову три способи обчислення$T(i, j):(1) i-1$ символів першої послідовності, вирівнюються з$j-1$ символами другої послідовності з максимальним балом$T(i-1, j-1)$, а$i$ й символ першої послідовності вирівнюється з $j$символ другої послідовності з оновленим максимальним балом$T(i-1, j-1)+S\left(a_{i}, b_{j}\right) ;(2) i-1$ символи першої послідовності вирівнюються з$j$ символами другої послідовності з максимальним балом$T(i-$$1, j)$, а $i$-й символ першої послідовності вирівнюється з проміжком у другій послідовності з оновленим максимальним балом$T(i-1, j)+g$, або; (3)$i$ символи першої послідовності вирівнюються з$j-1$ символами другої послідовності з максимальним оцінка$T(i, j-1)$, а проміжок у першій послідовності вирівнюється з$j$ символом другої послідовності з оновленим максимальним балом$T(i, j-1)+g$. Потім ми порівняємо ці три$T(i, j)$ бали і призначаємо бути максимальним; тобто

\[T(i, j)=\max \left\{\begin{array}{l} T(i-1, j-1)+S\left(a_{i}, b_{j}\right) \\[4pt] T(i-1, j)+g \\[4pt] T(i, j-1)+g \end{array}\right. \nonumber \]

Граничні умови дають оцінку вирівнювання послідовності з нульовою послідовністю проміжків, так що

\[T(i, 0)=T(0, i)=i g, \quad i>0 \nonumber \]

с$T(0,0)=0$.

Рекурсія$(7.2)$ разом з граничними умовами (7.3) може бути використана для побудови динамічної матриці. Оцінка найкращого вирівнювання потім задається останнім заповненим елементом матриці, який для вирівнювання послідовності довжини$n$ з послідовністю довжини$m$ дорівнює$T(n, m)$. Крім цієї оцінки, однак, ми також хочемо визначити сам вирівнювання. Вирівнювання може бути отримано шляхом трасування шляху в динамічній матриці, яка була дотримана для обчислення кожного елемента матриці$T(i, j)$. Там може бути більше одного шляху, так що найкраще вирівнювання може бути виродженим.

Вирівнювання послідовності завжди проводиться обчислювальним шляхом, і є відмінні програмні засоби, вільно доступні в Інтернеті (див. $7.6). Просто щоб проілюструвати алгоритм динамічного програмування, ми вручну обчислюємо динамічну матрицю для вирівнювання двох коротких послідовностей ДНК GGAT і GAATT, оцінюючи збіг як$+2$, невідповідність як$-1$ і індель як$-2$:

$\begin{array}{ccccccc} & - & \mathrm{G} & \mathrm{A} & \mathrm{A} & \mathrm{T} & \mathrm{T} \\[4pt] - & 0 & -2 & -4 & -6 & -8 & -10 \\[4pt] \mathrm{G} & -2 & 2 & 0 & -2 & -4 & -6 \\[4pt] \mathrm{G} & -4 & 0 & 1 & -1 & -3 & -5 \\[4pt] \mathrm{~A} & -6 & -2 & 2 & 3 & 1 & -1 \\[4pt] \mathrm{~T} & -8 & -4 & 0 & 1 & 5 & 3\end{array}$

У нашому ручному обчисленні дві послідовності, які потрібно вирівняти, йдуть вліво і над динамічною матрицею, ведучи з символом розриву '$^{\prime}$'. Рядок 0 та стовпчик 0 заповнюються граничними умовами, починаючи з 0 у позиції$(0,0)$ та збільшуючи штраф$-2$ за пробіл у рядку 0 та стовпці 0 вниз. Відношення рекурсії (7.2) потім використовується для заповнення динамічної матриці по одному рядку за раз, рухаючись зліва направо і зверху вниз. Для визначення елемента$(i, j)$ матриці необхідно порівняти три числа і взяти максимум: (1) оглянути нуклеотиди зліва від рядка$i$ і вище стовпця$j$ і додати$+2$ для збігу або$-1$ для невідповідність елементу$(i-1, j-1)$ матриці;$(2)$ додати$-2$ до елемента$(i-1, j)$ матриці;$(3)$ додати$-2$ до елементу$(i, j-1)$ матриці. Наприклад, перший обчислений елемент матриці 2 в позиції$(1,1)$ визначався взявши максимум$(1) 0+2=2$, так як$G-G$ є збігом;$(2)-2-2=-4 ;(3)-2-2=-4$. Ви можете перевірити своє розуміння динамічного програмування, обчисливши інші елементи матриці.

Після побудови матриці алгоритм traceback, який знаходить найкраще вирівнювання, починається з нижнього правого елемента матриці, тут елемент$(4,5)$ матриці з записом 3. Елемент матриці, який використовувався для обчислення 3, був або at$(4,4)$ (горизонтальний хід), або at$(3,4)$ (діагональний хід). Наявність двох можливостей означає, що найкраще вирівнювання вироджується. Поки ми довільно вибираємо хід по діагоналі. Будуємо вирівнювання від кінця до початку з GGAT зверху і GAATT знизу:

$\mathrm{T}$

Ми ілюструємо нашу поточну позицію в динамічній матриці, усуваючи всі елементи, які не знаходяться на шляху відстеження і більше не доступні:

$\begin{array}{ccccccc} & - & G & A & A & T & T \\[4pt] - & 0 & -2 & -4 & -6 & -8 & \\[4pt] G & -2 & 2 & 0 & -2 & -4 & \\[4pt] G & -4 & 0 & 1 & -1 & -3 & \\[4pt] A & -6 & -2 & 2 & 3 & 1 & \\[4pt] T & & & & & & 3\end{array}$

Починаємо знову з запису 1 в$(3,4)$. Це значення прийшло з запису 3 при$(3,3)$ горизонтальному переміщенні. Тому вирівнювання розширюється до

-Т

||
ТТ

де зазор вставляється у верхній послідовності для горизонтального ходу. (Зазор вставляється в нижній послідовності для вертикального переміщення.) Динамічна матриця тепер виглядає так

$\begin{array}{lcccccc} & - & G & A & A & T & T \\[4pt] - & 0 & -2 & -4 & -6 & & \\[4pt] G & -2 & 2 & 0 & -2 & & \\[4pt] G & -4 & 0 & 1 & -1 & & \\[4pt] A & -6 & -2 & 2 & 3 & 1 & \\[4pt] T & & & & & & 3\end{array}$

Починаючи знову з запису 3 в$(3,3)$, це значення прийшло з запису 1$(2,2)$ в діагональному ходу, розширюючи вирівнювання до

А-Т

|||
ATT Динамічна матриця тепер виглядає так

зображення

Продовжуючи в цьому моді (спробуйте зробити це), остаточне вирівнювання -

зображення

де прийнято представляти відповідний символ з двокрапкою '$:$'. Шляхом трасування в динамічній матриці є

зображення

Якщо спочатку був прийнятий інший вироджений шлях, остаточне вирівнювання буде

зображення

ГААТТ

і шлях відслідковування буде

зображення

Оцінка обох вирівнювань легко перераховується, щоб бути однаковою, з$2-1+2-$$2+2=3$ і$2-1+2+2-2=3$

Алгоритм вирівнювання двох білків аналогічний, за винятком відповідності і невідповідності балів залежать від пари вирівнюючих амінокислот. З двадцятьма різними амінокислотами, що містяться в білках, оцінка представлена матрицею$20 \times 20$ заміщення. Найбільш часто використовуваними матрицями є серії PAM та серії матриць BLOSUM, причому BLOSUM62 зазвичай використовується матриця за замовчуванням.