ФБТ БИ 2курс / протокол 4
.docxЛАБОРАТОРНА РОБОТА 4
ПОБУДОВА ПСЕВДОГЛОБАЛЬНОГО ВИРІВНЮВАННЯ
Мета роботи – ознайомитись з поняттям псевдоглобальне вирівнювання послідовностей нуклеотидних і амінокислотних та навчитися писати й використовувати програми псевдоглобального вирівнювання.
Теоретичні відомості
Псевдоглобальне вирівнювання не враховує деякі кінцеві пробіли в послідовностях, тобто ті, які стоять перед першим або після останнього символу. Наприклад, всі пробіли у другій послідовності кінцеві, на відміну від єдиного пробілу в першій.
AGACCAGATTTCTGCCAG (4)
– AGACTTAG – – – –
Відмітимо, що дві послідовності значно відрізняються за довжиною. Якщо б застосували основний алгоритм оптимального вирівнювання, то отримали б:
AGACCAGATTTCTGCCA (5)
AGA * C * * * * * Т * Т * * * AG
з вагою -12, на відміну від ваги (4) рівної -14. Вирівнювання (5), незважаючи на більшу вагу, гірше з точки зору пошуку співпадаючих фрагментів в послідовностях. Це відображує той факт, що, якщо не враховувати кінцеві пробіли, вага вирівнювання (4) дорівнює 3.
Опис алгоритму
Алгоритм псевдоглобального вирівнювання має мету вирівняти послідовності, не враховуючи початкові та кінцеві пробіли.
Цього можна домогтися за допомогою внесення лише однієї зміни у алгоритм глобального вирівнювання, а саме, якщо прибрати встановлення початкових штрафів у першому рядку та стовпчику.
Реалізація алгоритму
s1 = input("First sequence: ")
s2 = input("Second sequence: ")
s1 = "_" + s1
s2 = "_" + s2
p = []
for i in s1:
col = []
for j in s2:
col.append(0)
p.append(col)
for x in range(1, len(s1)):
for y in range(1, len(s2)):
left = p[x-1][y] - 2
up = p[x][y-1] - 2
if s1[x] == s2[y]:
slog = 1
else:
slog = -1
diag = p[x-1][y-1] + slog
p[x][y] = max(left, up, diag)
x = len(s1)-1
y = len(s2)-1
lastrow = []
lastcol = []
for s in p:
print (s)
for i in range(len(s2)):
lastrow.append(p[x][i])
for j in range(len(s1)):
lastcol.append(p[j][y])
maxrow = max(lastrow)
maxcol = max(lastcol)
print("Results for max in the last row: ")
for i in range(len(s2)):
if lastrow[i] == maxrow:
ymax = i
xmax = x
res1 = ""
res2 = ""
while xmax and ymax:
res1 = s1[xmax] + res1
res2 = s2[ymax] + res2
xmax = xmax - 1
ymax = ymax - 1
if ymax == 0:
while xmax:
res1 = s1[xmax] + res1
res2 = "_" + res2
xmax = xmax - 1
if xmax == 0:
while ymax:
res1 = "_" + res1
res2 = s2[ymax] + res2
ymax = ymax - 1
print("Resulting sequence 1: " + res1)
print("Resulting sequence 2: " + res2)
print("Results for max in the last column: ")
for j in range(len(s1)):
if lastcol[j] == maxcol:
ymax = y
xmax = j
res1 = ""
res2 = ""
while xmax and ymax:
res1 = s1[xmax] + res1
res2 = s2[ymax] + res2
xmax = xmax - 1
ymax = ymax - 1
if ymax == 0:
while xmax:
res1 = s1[xmax] + res1
res2 = "_" + res2
xmax = xmax - 1
if xmax == 0:
while ymax:
res1 = "_" + res1
res2 = s2[ymax] + res2
ymax = ymax - 1
print("Resulting sequence 1: " + res1)
print("Resulting sequence 2: " + res2)
Обладнання
Комп’ютер з встановленим Python та текстовим редактором.
Порядок виконання роботи
1. Ознайомитися з методом псевдоглобального вирівнювання.
2. Написати програму для реалізації алгоритму псевдоглобального вирівнювання.
3. Провести вирівнювання тестового прикладу послідовності відповідно до варіанту без допомоги програми.
4. Перевірити правильність ручних розрахунків за допомогою програми.