Лабораторна робота 3 побудова псевдоглобального вирівнювання

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

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

Псевдоглобальне вирівнювання не враховує деякі кінцеві пробіли в послідовностях, тобто ті, які стоять перед першим або після останнього символу. Наприклад, всі пробіли у другій послідовності кінцеві, на відміну від єдиного пробілу в першій.

AGACCAGATTTCTGCCAG (4)

– AGACTTAG – – – –

Відмітимо, що дві послідовності значно відрізняються за довжиною. Якщо б застосували основний алгоритм оптимального вирівнювання, то отримали б:

AGACCAGATTTCTGCCA (5)

AGA * C * * * * * Т * Т * * * AG

з вагою -12, на відміну від ваги (4) рівної -14. Вирівнювання (5), незважаючи на більшу вагу, гірше з точки зору пошуку співпадаючих фрагментів в послідовностях. Це відображує той факт, що, якщо не враховувати кінцеві пробіли, вага вирівнювання (4) дорівнює 3.

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

Алгоритм псевдоглобального вирівнювання має мету вирівняти послідовності, не враховуючи початкові та кінцеві пробіли.

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

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

#Псевдоглобальне вирівнювання

# Є 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

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

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'

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

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

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

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

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

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

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

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

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

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

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

resSeq1 = ''

resSeq2 = ''

x = len(s1)

y = len(s2)

#Тепер йдемо з кінця (x і y будуть рівними довжині першої та другої #послідовностей) до початку

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)