7.4: Прогалини

Емпіричні дані свідчать про те, що розриви кластерні, як в нуклеотидних, так і в білкових послідовностях. Кластеризація зазвичай моделюється різними штрафами за відкриття зазору\(\left(g_{o}\right)\) і розширення зазору\(\left(g_{e}\right)\), с\(g_{o}<g_{e}<0\). Наприклад, схема оцінки за замовчуванням для широко використовуваного програмного забезпечення BLASTN призначений\(+1\) для нуклеотидного матчу,\(-3\) для невідповідності нуклеотидів,\(-5\) для відкриття розриву та\(-2\) для розширення розриву.

Наявність двох типів зазорів (відкриття і розширення) ускладнює алгоритм динамічного програмування. Коли індель додається до існуючого вирівнювання, приріст скорингу залежить від того, чи є індель відкриттям зазору або розширенням зазору. Наприклад, розширене вирівнювання

\[\begin{array}{ll} \mathrm{AB} & \mathrm{AB}- \\[4pt] 11 & \text { to } & 111 \\[4pt] \mathrm{ab} & & \mathrm{abc} \end{array} \nonumber \]

додає штраф за відкриття розриву\(g_{o}\) до рахунку, тоді як

\[\begin{array}{ll} \text { A- } & \text { A- } \\[4pt] \text { II to } & \text { ||| } \\[4pt] \text { ab } & & \text { abc } \end{array} \nonumber \]

додає штраф за розширення розриву\(g_{e}\) до рахунку. Приріст балів залежить не тільки від поточної вирівнюючої пари, але і від раніше вирівняної пари.

Остаточна пара вирівнювання послідовності довжини\(i\) з послідовністю довжини\(j\) може бути однією з трьох можливостей (верх:низ): (1)\(a_{i}: b_{j} ;\) (2)\(a_{i}:-;(3)-: b_{j}\). Тільки для (1) приріст балів\(S\left(a_{i}, b_{j}\right)\) однозначний. Для (2) або (3) приріст балів залежить від наявності або відсутності інделів у раніше вирівняних символах. Наприклад, для вирівнювання, що закінчуються на\(a_{i}:-\), раніше вирівняна пара символів може бути однією з (i)\(a_{i-1}: b_{j}\), (ii)\(-: b_{j}\), (iii)\(a_{i-1}:-\). Якщо попередня вирівняна пара символів була (i) або (ii), приріст балів буде штрафом за відкриття розриву\(g_{o}\); якщо це було (iii), приріст балів буде штрафом за розширення розриву\(g_{e}\).

Щоб прибрати неоднозначність, яка виникає з єдиною динамічною матрицею, нам потрібно обчислити одночасно три динамічні матриці, причому елементи матриці позначаються\(T(i, j), T_{-}(i, j)\) і\(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-1)+S\left(a_{i}, b_{j}\right) \\[4pt] T^{-}(i-1, j-1)+S\left(a_{i}, b_{j}\right) \end{array}\right. \nonumber \]

(2)\(a_{i}:-\)

\[T_{-}(i, j)=\max \left\{\begin{array}{l} T(i-1, j)+g_{o} \\[4pt] T_{-}(i-1, j)+g_{e} \\[4pt] T^{-}(i-1, j)+g_{o} \end{array}\right. \nonumber \]

(3)\(-: b_{j}\)

\[T^{-}(i, j)=\max \left\{\begin{array}{l} T(i, j-1)+g_{o} \\[4pt] T_{-}(i, j-1)+g_{o} \\[4pt] T^{-}(i, j-1)+g_{e} \end{array}\right. \nonumber \]

Щоб вирівняти послідовність довжини\(n\) з послідовністю довжини\(m\), найкращим показником вирівнювання є максимум балів, отриманих з трьох динамічних матриць:

\[T_{\text {opt }}(n, m)=\max \left\{\begin{array}{l} T(n, m), \\[4pt] T_{-}(n, m), \\[4pt] T^{-}(n, m) . \end{array}\right. \nonumber \]

Алгоритм traceback для пошуку найкращого вирівнювання триває, як і раніше, починаючи з елемента матриці, що відповідає найкращому оцінці вирівнювання\(T_{\mathrm{opt}}(n, m)\), і трасування назад до елемента матриці, який визначив цю оцінку. Оптимальне вирівнювання потім будується від останнього до першого, як і раніше, але тепер може відбуватися перемикання між трьома динамічними матрицями.