Лабораторна робота

з дисципліни «Основи біоінформатики»

		Виконала: студентка 2 курсу, групи БІ-11 Вітюк В.І.

Київ – 2013

Алгоритм Нідлмана-Вунша (англ. Needleman-Wunsch algorithm) — один із алгоритмів вирівнювання послідовностей, який належить до динамічного програмування, та є глобальним вирівнюванням.

Складається цей алгоритм із трьох послідовних етапів:

1. Побудова ініціюючої матриці

Для цього дві порівнювані послідовності розташовують як верхній рядок і як нижні, тобто вони є заголовками матриці. Крім того перед кожною послідовністю виставляють пропуск. І заповнюють перший стовпчик і перший рядок. Заповнення відбувається за допомогою штафу за пенальті (так як найперше значення в рядку і стовпчику — це пропуск, отже, і перший рядок із стовпичок будуть заповнені від’ємними значеннями).

2. Заповнення таблиці

На основі цієї матриці будується матриця локалізації. Слідкують за тим, як відбувалося заповнення, тобто з якої комірки було отримано максимальне значення для наступної комірки.

3. Пошук максимального вирівнювання

Пошук починають із останньої кутової комірки, а завершують завжди найпершою коміркою. Вирівнювання відбувається таким чином: необхідно на основі матриці локалізації створити шлях, який ґрунтується на «вказівках» кожної комірки. Буква D — діагональ, тобто необхідно перейти на комірку, що розташована по діагоналі, T — вершина, треба перейти на 1 комірку вгору (біологічно це означає, що у горизонтальній послідовності була делеція, або у вертикальній — інсерція), L — вліво, треба перейти до комірки, розташованої праворуч (біологічний сенс обернений до попереднього). Якщо комірка має два значення, то можливі два напрямки руху, три — три.

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

# глобальное выравнивание

# есть 2 строки которые состоят из 4-буквенного алфавита

# 1. ввести строки.

s1 = input ('enter first sequence:')

s2 = input ('enter second sequence:')

# 2. составить матрицу совпадения символов (создать и заполнить первую строку

# и столбец).

p = []

for x in range (len(s1)+1): #широко применяется цикл for, который представляет собой цикл обхода заданного множества элементов (символов строки, объектов списка или словаря) и выполнения в своем теле различных операций над ними. Например, если имеется список чисел, и необходимо увеличить значение каждого элемента на единицу, то можно перебрать список с помощью цикла for, выполнив над каждым его элементом соответствующее действие.

row = []

for y in range (len (s2) + 1): #Как правило, циклы for используются либо для повторения какой-либо последовательности действий заданное число раз, либо для изменения значения переменной в цикле от некоторого начального значения до некоторого конечного.

Для повторения цикла некоторое заданное число раз можно использовать цикл for вместе с функцией range.

row.append (0)

p.append (row)

for x in range (len (s1) +1): #имеется список чисел, и необходимо умножить каждое число на две единицы, то можно перебрать список с помощью цикла for, выполнив над каждым его элементом соответствующее действие. Заполняется первый ряд матрици.

p[x][0] = x * (-2)

for y in range (len (s2) +1): #Заполняется первый столбик матрици.

p[0][y] = y * (-2)

# 3. создать матрицу путей.

way = []

for x in range (len(s1)+1): #нахождение пути выравнивания

row = []

for y in range (len (s2) + 1): #начинается с последней ячейки

row.append (0)

way.append (row)

# 4. заполнить остальную матрицу и не забывать заполнять матрицу путей.

# как заполняется матрица:

# 1 вариант: а(x,y-1)-2

# 2 вариант: a (x-1, y-1)+D(x,y), где D(х,у)=1, если s1 [x]==s2[y]; иначе -1.

# 3 вариант: a (x-1, y) -2

# Нужно выбрать максимальный вариант.

for x in range (1, len (s1) +1):

for y in range (1, len (s2) +1):

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

if s1[x-1]== s2 [y-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)

# если элемент матрицы равен дигональ, то:

# добавляем буквы в результирующие последовательности, переходим к элементу (х-1, у-1)

# если элемент матрицы путей равен верх, то:

# в первой последовательности ставим пробел, а во второй букву, переходим к элементу(х, у-1)

# если элемент матрицы путей равен лево, то:

# во второй последовательности ставим пробел, а в первой букву, переходим к элементу (х-1, у)

resseq1 = ''

resseq2 = ''

x = len (s1) +1

y = len (s2) +1

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

#TODO Reverse resulting sequence

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

print ('first sequence:' + s1)

print ('second sequence:' +s2)

print ('P(i,j):' +str (p))

print (' way matrix: '+ str (way))

print ('first resulting sequence: '+ resseq1)

print ('second resulting sequence: '+ resseq2)

Вывод: Вирівнювання послідовностей в біоінформатиці — метод порявняння нуклеотидних (ДНК, РНК) або пептидних (білки) послідовностій шляхом знаходження схожих ділянок, що може бути наслідком функціональних, структурних або еволюційних взаємини між послідовностями. Вирівняні послідовності нуклеотидів або амінокислотних залишків зазвичай представляються у вигляді рядків в матриці. Між залишками вставляються пропуски таким чином, що залишки з ідентичними або подібними особливостями вирівнюються в послідовних колонках. Дуже короткі або дуже подібні послідовності можуть бути вирівняні вручну; проте, найцікавіші проблеми вимагають вирівнювання довгих, надзвичайно варіабельних послідовностей або надзвичайно великого їх числа, що неможливо зробити виключно людськими зусиллями. Обчислення глобального вирівнювання — форма глобальної оптимізації, що «вимушує» вирівнювання охопити повну довжину всіх послідовностей у запиті.

Дата добавления: 2015-07-13