Лабораторна робота 4 загальна функція штрафу

Мета роботи – ознайомитись з поняттям загальної функції штрафута навчитися програмувати алгоритм вирівнювання символьних послідовностей з використанням загальної функції штрафу.

Теоретичні відомості

Визначимо розрив (gap) в послідовності як послідовну кількість k>1 пробілів. З урахуванням виникнення можливих мутацій, поява розриву з k пробілами більш вірогідна, ніж поява k незалежних пробілів. Це пов’язане з тим, що поява тривалого розриву може бути результатом лише однієї делеції (мутації), в той час як k пробілів утворюються через k мутацій, а виникнення однієї мутаційної події більш вірогідне, ніж декількох. Блочне вирівнювання враховує можливу кластеризацію пробілів.

Позначимо w(k) функцію штрафу розриву з k пробілами. Ми рахували w(k)=gk, де g – величина штрафу за індивідуальний пробіл, k – кількість пробілів.

Опис алгоритму

Розглянемо алгоритм подібності з урахуванням загальної функції штрафування розривів w(k), алгоритмічна складність якого О(n³) для двох послідовностей довжини n. Відмінності з основним алгоритмом виникають через неадитивну схему штрафів. Кожне вирівнювання тепер можна розкласти на суму послідовних блоків трьох типів:

1. два символи;

2. максимальна серія послідовних символів в t, вирівняна з пробілами в s;

3. максимальна серія послідовних символів в s, вирівняна з пробілами в t.

Серія максимальна в тому сенсі, що не може бути продовжена далі. На рис. 2 представлено блочне вирівнювання блоки першого типу одержують бал p(i, j), де і та j – символи, що вирівнюються. Блоки типу 2 та 3 одержують бал w(k), де k – довжина розриву.

s1 T T G - - - T T A A G GCT G A T G

s2 T G A T C C A - - - - - - G C G - -

s1 T| T| G| - - - | T| T A A G G C| T G A| T G

s2 T| G| A| T G G| A| - - - - - -| G C G| - -

Рис. 2. Блочне вирівнювання.

Тепер вага вирівнювання розраховується на рівні блоків. Адитивність ваг зберігається тільки на межах блоків, що призводить до деяких змін в основному алгоритмі. Блоки не можуть йти довільно один за одним, блоки типу 2 і 3 не можуть йти за блоками того ж типу. Для кожної пари [i, j] тепер зберігається не значення ваги найкращого вирівнювання між префіксами s[1…i] й t[1…j], а вага вирівнювання між їх останніми блоками певного типу.

Для порівняння послідовності s довжини m та послідовності t довжини n використовують три масиви розміру (m+1)(n+1): a – для порівняння символьних блоків; b – для порівняння блоків, що закінчуються пробілами в s; с – для порівняння блоків, що закінчуються пробілами в t. Масиви ініціюються за наступними формулами:

a[i, 0] = w(i)

b[i, 0] = w(i)

с[i, 0] = w(i)

a[0, j] = w(j)

b[0, j] = w(j)

c[0, j] = w(j)

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

a[i, j] = p(i, j)+max{a(i-1,j-1), b(i-1,j-1), c(i-1,j-1)}

b[i,j] = max{a[i,j-k]-w(k), c[i,j-k]-w(k)}, 1≤k≤j;

c[i,j]=max{a[i-k,j]-w(k), b[i-k,j]-w(k)}, 1≤k≤i.

Відмітимо, що значення масивів b та c залежать від декількох величин, оскільки останній блок може мати різну довжину. Для одержання значення максимальної ваги вирівнювання береться максимум по всім a[m,n], b[m,n], c[m,n]. Для вирівнювання використовується та ж ідея, що і в інших алгоритмах. Ми вибираємо елементи масивів з максимальною вагою, запам’ятовуючи масив якого типу було використано.