Автор работы: Пользователь скрыл имя, 03 Мая 2013 в 16:04, лабораторная работа
Вирівнювання послідовностей в біоінформатиці — метод порівняння нуклеотидних (ДНК, РНК) або пептидних (білки) послідовностій шляхом знаходження схожих ділянок, що може бути наслідком функціональних, структурних або еволюційних взаємини між послідовностями. Вирівняні послідовності нуклеотидів або амінокислотних залишків зазвичай представляються у вигляді рядків в матриці. Між залишками вставляються пропуски таким чином, що залишки з ідентичними або подібними особливостями вирівнюються в послідовних колонках.
Міністерство освіти і науки України
Національний технічний університет України
«Київський політехнічний інститут»
Факультет біотехнології і біотехніки
Кафедра промислової біотехнології
Лабораторна робота №4
з курсу: «Біоінформатика»
на тему:
«Алгоритм швидкого
вирівнювання»
Виконала:
студентка ІV курсу
групи БТ-91
Ростем Я.Ю.
Київ – 2013
Теоретичні відомості
Вирівнювання послідовностей в біоінформатиці — метод порівняння нуклеотидних (ДНК, РНК) або пептидних (білки) послідовностій шляхом знаходження схожих ділянок, що може бути наслідком функціональних, структурних або еволюційних взаємини між послідовностями. Вирівняні послідовності нуклеотидів або амінокислотних залишків зазвичай представляються у вигляді рядків в матриці. Між залишками вставляються пропуски таким чином, що залишки з ідентичними або подібними особливостями вирівнюються в послідовних колонках.
Розглянемо алгоритм швидкого вирівнювання подібних послідовностей (лише для випадку глобального вирівнювання), коли порівнюються послідовності однакової довжини n. В цьому випадку масив a(i, j) стає квадратною матрицею і по головній діагоналі розміщено вирівнювання без пробілів між s i t. Якщо таке вирівнювання не оптимальне, то необхідно ввести пробіли для одержання більшої ваги. Пробіли завжди вводяться попарно, один в s і один в t. Вирівнювання ведеться поблизу головної діагоналі.
Основна ідея полягає в тому, що у випадку схожих послідовностей, найкраще вирівнювання лежить в малому оточенні головної діагоналі. Розглянемо приклад алгоритму для заповнення матриці в горизонтальній та вертикальній смузі шириною 2k +1 навколо головної діагоналі (рис.4.2).
Рис. 4.2 Масив ваг вирівнювання префіксів а для порівняння подібних послідовностей однакової довжини
Елемент a(n,n) містить максимальну вагу вирівнювання в смузі заданої ширини. Відмітимо, що значення поза смугою ширини k не використовуються івідповідно не розраховуються. Для того, щоб визначити, чи лежить позиція (i,j) всередині смуги, використовується проста перевірка -k ≤i - j ≤k.
Як i в інших алгоритмах динамічного програмування, кожен елемент a(i,j)
залежить лише від трьох попередніх значень: a(i-1,j),a(i-1,j-1), a(i,j-1).
Але перевіряти елемент a(i-1,j-1) не обов’язково, оскільки він знаходиться на тій самій діагоналі, що і елемент a(i,j), і завжди буде знаходитися всередині смуги. Перевіряти потрібно елементи a(i-1,j), a(i,j-1), котрі можуть виходити за межі смуги, за умови того, що елемент a(i,j) знаходиться всередині неї.
Модифікація основного алгоритму для вирівнювання подібних
послідовностей
• Ініціалізація
першого рядка і стовпчика масиву ваг
префіксів а: перші k
елементів рядка
і стовпчика обчислюються за формулою!
а(0,j)=0, i = 0,..k,
де
а(і,0)=0, j = 0,..k.
(величина k наперед задана).
• Заповнення частини таблиці (рис 4.2), що знаходиться у смузі шириною
2k + 1, за наступним принципом:
Якщо елемент a(i - 1,j) знаходиться всередині смуги, тоді:
Якщо елемент a(i,j -1) знаходиться всередині смуги, тоді:
Очевидно, що у випадку коли обидва елементи a(i-1,j) та a(i,j-1) знаходяться всередині смуги, тоді елемент a(i,j) потрібно розраховувати зa вже відомою формулою (4.2).
Після першого проходження алгоритму, якщо одержане значения а(n,n) для фіксованого значения k більше, або дорівнює вазі найкращого вирівнювання з k+1 пробілами, у такому випадку знайдено оптимальне вирівнювання. Враховуючи, що у вирівнюванні присутні принаймні k+1 пар пробілів, то можливо найкраща вага вирівнювання дорівнює M[n-(k+1)]+2(k+1)g. Ця величина вираховується з припущенням, що у вирівнюванні знаходиться точно k+1 пара пробілів, а усі інші пари дають співпадіння (М > 0 - вага співпадіння).
Якщо а(n,n) менше цієї величини, ширина смуги подвоюється і знову розраховується а(n,n). Описаний метод можна розширити і для послідовностей різної довжини.
4.5. Загальна функція штрафу
Визначимо розрив в послідовності як безперервну кількість k > 1 пробілів. 3 урахуванням виникнення можливих мутацій, поява розриву з k пробілами більш ймовірна, ніж поява к незалежних пробілів. Це пов’язано з тим, що поява довгого розриву може бути результатом лише однієї делеції, в той час як к пробілів, розділених блоками «символ-символ», утворюються через k мутацій, а виникнення однієї мутаційної події більш ймовірне, ніж декількох. Блочне вирівнювання враховує можливу кластеризацію пробілів.
Позначимо ω(k) функцію штрафу розриву з к пробілами. ω(k)=gk, де g -величина штрафу за індивідуальний пробіл, k - кількість пробілів.
Відмінності між алгоритмом подібності послідовностей з урахуванням загальної функції штрафу та основним алгоритмом виникають через неадитивну схему штрафів. Кожне вирівнювання тепер можна розкласти на суму послідовних блоків трьох типів:
Розглянемо наступне блочне вирівнювання.
TTG_ _ _TTAAGGCTGATG
TGATCCA _ _ _ _ _ _ GCG_ _
T|T|G|_ _ _ |T|TAAGGC|TGA|TG
T|G|A|TGG|A| _ _ _ _ _ _ |GCG|_ _
Блоки першого типу одержують вагу p(i, j), де і та j – символи, що вирівнюються. Блоки другого та третього типів одержують вагу w(k), де k – довжина розриву.
Тепер вага вирівнювання розраховується на рівні блоків. Адитивність ваг зберігається тільки на межах блоків, що призводить до деяких змін в основному алгоритмі. Блоки не можуть йти довільно один за одним, блоки другого та третього типів не можуть йти за блоками того ж типу. Для кожної пари (i, j) тепер зберігається не значення ваги найкращого вирівнювання між префіксом t, довжиною i та префіксом s, довжиною j, а вага вирівнювання між їх останніми блоками певного типу.
Для порівняння послідовності t довжиною m та послідовності s довжиною n використовують три масиви розміру (m +1)(n +1):
Масив a – для порівняння символьних блоків;
Масив b – для порівняння блоків, що закінчуються пробілами в t;
Масив с – для порівняння блоків, що закінчуються пробілами в s.
Алгоритм подібності з урахуванням загальної функції штрафу
Масиви ініціюються за наступними формулами:
3) Розрахунок усіх інших елементів масивів a,b,c.
В залежності від типу блоку, яким закінчується вирівнювання, змінюються значення у відповідних масивах за рекурентними формулами:
Відмітимо, що значення масивів b і c залежать від декількох величин, оскільки останній блок може мати різну довжину.
4) Пошук максимального з трьох елементів a(m,n), b(m,n), c(m,n) та
вибір стартової точки.
Для одержання значення максимальної ваги вирівнювання береться максимум по всім a(m,n), b(m,n), c(m,n).
5) Побудова вирівнювання на основі значень елементів масивів a, b, c.
Для вирівнювання використовується та ж ідея, що і в інших алгоритмах. Ми вибираємо елементи масивів з максимальною вагою, запам’ятовуючи масив якого типу було використано.
Програма алгоритму швидкого вирівнювання
#Швидке вирівнювання
#2 строки из 4-х буквенногоалфавита
#1. Ввести строки
s1=input('Enterfirstsequense:'
s2=input('Entersecondsequense:
#2. Составитьматрицусовпадения и несовпадения (создать и заполнить
# первую строку и столбец)
p=[]
for x inrange(len(s1)+1): #commentit: Заповнюємо перший стовпчик.
row = []
for y inrange(len(s2)+1): #commentit: Заповнюємо першу строчку.
row.append(0)
p.append(row)
for x inrange(len(s1)+1): #commentit: забити 1-й ряд масиву арифметичною
прогресією з коефіцієнтом -2, і початком в 0
p[x][0]=x*(-2)
for y inrange(len(s2)+1):
p[0][y]=y*(-2)
#3. Создатьматрицу путей
way=[]
for x inrange(len(s1)+1): #commentit: Робимо масив з нулів, використовуючи цикл for. Заповнюємо стовпчик.
row = []
for y inrange(len(s2)+1): #commentit: Робимо масив з нулів, використовуючи цикл for. Заповнюємо стовпчик.
row.append(0)
way.append(row)
#4. Заполнитьматрицу, не забытьматрицу путей
#Як заповнюється матриця
#1-й в:p(x;y-1)-2
#2-й в:p(x-1;y)-2
#3-й в:p(x-1;y-1)+D(x;y), де D(x;y)=1, якщо s1[x]==s2[y]; інакше -1
# вибрати макс варіант
for x inrange (1, len(s1)+1):
for y inrange (1, len(s2)+1):
if ( y>(x+1)):
p[x][y]=0
else:
if (x>(y+1)):
p[x][y]=0
else:
first = p[x][y-1]-2
if s1[x-1]==s2[y-1]: #commentit (about +- 1 indexes): Розраховуємо елемент, що вище на стовпчик. Якщо буква на перетині комірки, яку розраховуємо однакова, то додаємо одиницю. Якшонеспівпадіння, то віднімаємо одиницю.
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. По матрице путей составитьрезульт. последовательности
# startingfromtheend. (len(s1)+1, len(S2)+1)
# if a matrixelementequalsdiag,
# addletterstotheresultsequences
# if a matrixelementequalsup
# switchovertotheelement (x, y-1)
# if a matrixelementequalsleft
# switchovertotheelement (x-1, y)
Result_sequence_1 = ''
Result_sequence_2 = ''
x=len(s1)
y=len(s2)
#commentit: Виводимо результуючу послідовність. Починаємо з кінця заповняти.
while (x>0 and y>0):
if (way[x][y]=='up'):
Result_sequence_1 = Result_sequence_1 + '_'
Result_sequence_2 = Result_sequence_2 + s2[y-1]
y=y-1
else:
if (way[x][y]=='left'):
Result_sequence_2 = Result_sequence_2 + '_'
Result_sequence_1 = Result_sequence_1 + s1[x-1]
x=x-1
else:
Result_sequence_1 = Result_sequence_1 + s1[x-1]
Result_sequence_2 = Result_sequence_2 + s2[y-1]
x=x-1
y=y-1
#6. Вивести результати
print('Firstsequense:'+s1)
print('Secondsequense:'+s2)
print('P(i;j)'+str(p))
print('Waymatrix: ' +str(way))
print('Firstresultingsequence: ' + Result_sequence_1[::-1])
print('
Демонстрація роботи програми
1 послідовність: (Feliscatuskeratin 72 mRNA, partialcds): gtgcggttcctggagcagca
2 послідовність (JP 2012523228-A/158: GENETIC TEST FOR LIVER COPPER ACCUMULATION IN DOGS): agtatgagtgtggattcggt