7.5: Локальні вирівнювання

Last updated
Save as PDF

Page ID: 66643

\( \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}}\)

Ми досі обговорювали, як вирівняти дві послідовності по всій їх довжині, що називається глобальним вирівнюванням. Однак часто корисніше вирівняти дві послідовності лише над частиною їх довжин, званих локальним вирівнюванням. У біоінформатиці алгоритм глобального вирівнювання називається «Needleman-Wunsch», а що для локального вирівнювання «Сміт-Уотерман». Локальні вирівнювання корисні, наприклад, при пошуку довгої послідовності геному для вирівнювання до короткого сегмента ДНК. Вони також корисні при вирівнюванні двох білкових послідовностей, оскільки білки можуть складатися з декількох доменів, і тільки один домен може вирівнюватися.

Якщо для простоти розглядати постійну величину зазору\(g\), то локальне вирівнювання можна отримати за допомогою правила

\[T(i, j)=\max \left\{\begin{array}{l} 0, \\[4pt] 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 \]

Після обчислення динамічної матриці за допомогою (7.8) алгоритм traceback починається з елемента матриці з найвищим балом і зупиняється на першому зустріненому нульовому балі.

Якщо ми застосуємо алгоритм Сміта-Уотермана для локально вирівнювання двох послідовностей, розглянутих раніше GGAT і GAATT, з відповідністю\(+2\), забитим як, невідповідність as\(-1\) і indel as\(-2\), динамічна матриця

\(\begin{array}{ccccccc} & - & \mathrm{G} & \mathrm{A} & \mathrm{A} & \mathrm{T} & \mathrm{T} \\[4pt] - & 0 & 0 & 0 & 0 & 0 & 0 \\[4pt] \mathrm{G} & 0 & 2 & 0 & 0 & 0 & 0 \\[4pt] \mathrm{G} & 0 & 2 & 1 & 0 & 0 & 0 \\[4pt] \mathrm{~A} & 0 & 0 & 4 & 3 & 1 & 0 \\[4pt] \mathrm{~T} & 0 & 0 & 2 & 3 & 5 & 3\end{array}\)

Алгоритм traceback починається з найвищого балу, тут 5 в матричному елементі\((4,4)\), і закінчується на 0 в матричному елементі\((0,0)\). Отримане локальне вирівнювання

\[\begin{gathered} :: \\[4pt] \text { GAAT } \end{gathered} \nonumber \]

який має оцінку п'ять, більше, ніж попередній глобальний показник вирівнювання в три.