Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ФБТ БИ 2курс / протокол 2

.docx
Скачиваний:
27
Добавлен:
10.04.2018
Размер:
19.02 Кб
Скачать

ЛАБОРАТОРНА РОБОТА 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).

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

s1 = input("First sequence: ")

s2 = input("Second sequence: ")

p = []

for i in s1:

row = []

for j in s2:

row.append(0)

p.append(row)

for y in range(len(s2)):

for x in range(len(s1)):

if (s1[x] == s2[y]):

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

m = max([a for b in p for a in b])

for x in range(len(s1)):

for y in range(len(s2)):

if p[x][y] == m:

xmax = x

ymax = y

for s in p:

print(s)

res1 = ""

res2 = ""

while m:

res1 = s1[xmax] + res1

res2 = s2[ymax] + res2

xmax = xmax - 1

ymax = ymax - 1

m = m-1

print("Resulting sequence 1: " + res1)

print("Resulting sequence 2: " + res2)

Обладнання

Комп’ютер з встановленим Python та текстовим редактором.

Порядок виконання роботи

  1. Ознайомитися з методом локального вирівнювання.

  2. Написати програму для реалізації алгоритму локального вирівнювання.

  3. Провести вирівнювання тестового прикладу послідовності відповідно до варіанту без допомоги програми.

  4. Перевірити правильність ручних розрахунків за допомогою програми.

Соседние файлы в папке ФБТ БИ 2курс