Лабораторна робота 2 побудова локального вирівнювання

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

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

Локальне вирівнювання s, t, це вирівнювання підрядка s з підрядком t.

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

Алгоритм пошуку оптимального локального вирівнювання є модифікацією основного алгоритму. З точки зору реалізації – маємо лише 3 відмінності від алгоритму глобального вирівнювання, а саме:

1. У локальному вирівнюванні відсутні початкові штрафи.

2. Матриця ваг не містить від’ємних значень, тобто, коли ми отримуємо значення, що менше за нуль, замінюємо його на 0.

3. Зворотній шлях починається не з останнього елементу матриці ваг, а з максимального.

Всі ці зміни у алгоритмі дозволяють знаходити саме ті підпослідовності, що максимально співпадають.

Складність алгоритму:

Створення матриць ваг та шляхів буде мати складність O(n∙m).

Розрахункова частина алгоритму займає O(n∙m).

Пошук максимального елемента коштує O(n∙m).

Зворотній хід – від O(min(n,m)) до O(max(n,m)).

Тобто загальна складність буде O(n∙m).

Реалізація алгоритму

#Локальне вирівнювання

# Є 2 рядки, які складаються з 4-х літерного алфавіту

#1. Ввести рядки

s1 = input('Enter first sequence:')

s2 = input('Enter second sequence:')

#2. Скласти матрицю співпадіння символів ( створити і заповнити #першу строку і стовпчик).

p = []

for x inrange(len(s1)+1): # Заповнюємо зовнішній масив

row = []

for y in range(len(s2)+1): # Заповнюємо внутрішній масив

row.append(0)

p.append(row)

#3. Створити матрицю шляхів.

way = []

for x inrange(len(s1)+1): #Заповнюємо зовнішній масив

row = []

for y inrange(len(s2)+1): # Заповнюємо внутрішній масив

row.append(0)

way.append(row)

#4. Заповнити всю матрицю. Та не забути заповнити матрицю шляхів.

# Як заповнюється матриця:

#Перший варіант: p(x,y-1)-2

#Другий варіант: p(x-1,y-1) + D(x,y), где D(x,y) = 1, якщо s1[x]==s2[y]; інакше -1.

#Третій варіант: p(x-1,y)-2

#Якщо у результуюче значення є від’ємним – потрібно поставити 0.

#Потрібно вибрати максимальний варіант.

for x inrange(1, len(s1)+1):

for y inrange(1, len(s2)+1):

first = p[x][y-1] - 2

if s1[x-1]==s2[y-1]: #Доданок в даному випадку буде #+1 або ж -1, в залежності

D = 1 #від того, чи співпадають відповідні #символи в послідовностях, чи ні

else:

D = -1

second = p[x-1][y-1] + D

third = p[x-1][y] - 2

p[x][y] = max(first, second, third) #Результуюче значення буде #знаходитись, як максимальне з #розрахованих вище

# Потрібно запам’ятати в матриці шляхи, звідки ми прийшли

if (p[x][y] == first):

way[x][y] = 'up'

if (p[x][y] == second):

way[x][y] = 'diag'

if (p[x][y] == third):

way[x][y] = 'left' if (p[x][y] < 0): #Якщо отримали значення менше за 0 – присвоюємо 0.

p[x][y] = 0

#5. За матрицею шляхів скласти результуючі послідовності.

#Йдемо з кінця в початок. (len(s1)+1, len(s2)+1)

#Якщо елемент матриці шляхів дорівнює діагональ то:

#додаємо букви до результуючої послідовності, переходимо

#до елементу (x-1,y-1)

#Якщо елемент матриці шляхів дорівнює верх, то:

#В першій послідовності ставимо пробіл, а в другій букву,

#переходимо до елементу (x,y-1)

# Якщо елемент матриці шляхів дорівнює ліво, то:

#У другій послідовності ставимо пробіл, а в першій букву,

#переходимо до елементу (x-1,y)

resSeq1 = ''

resSeq2 = ''

#Знайдемо координати максимального елементу у матриці ваг

x = 0

y = 0

max = 0

for i in range(1, len(s1)):

for j in range(1, len(s2)):

if (p[i][j] >= max):

x = i

y = j

max = p[i][j]

#Тепер йдемо зі знайденої координати максимального елемента #послідовності до початку

while (x>0 and y>0):

if (way[x][y] == 'up'):

resSeq1 = resSeq1 + '_'

resSeq2 = resSeq2 + s2[y-1]

y = y - 1

else:

if (way[x][y] == 'left'):

resSeq2 = resSeq2 + '_'

resSeq1 = resSeq1 + s1[x-1]

x = x - 1

else:

resSeq1 = resSeq1 + s1[x-1]

resSeq2 = resSeq2 + s2[y-1]

x = x - 1

y = y - 1

#Вивести результати

print('First sequence: ' + s1)

print('Second sequence: ' + s2)

print('P(i,j):')

for row in p:

print(row)

print('Way matrix: ')

for row in way:

print(row)

print('First resulting sequence: ' + resSeq1)

print('Second resulting sequence: ' + resSeq2)