Обладнання

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

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

1. Ознайомитися з вирівнювання за допомогою алгоритму загальної функції штрафу.

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

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

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

Тестові приклади

1	s C A T T A A A T tCA TT A	Фрагмент ДНК людини [2]
2	s C T A T A A T A t A T A A T	Фрагмент ДНК людини [2]
3	s G A A A C T G G t A C T G G	Фрагмент ДНК миші [2]
4	s A G T T A A A C t T A A A C	Фрагмент ДНКпацюка [2]
5	s A C A T G C A A t G C A A A	Фрагмент ДНК Drosophila [2]
6	s G T A T A C A A t C A A A G	Фрагмент ДНК E. coli [3]
7	S G G A T C C G A A t G A A A T	Фрагмент ДНК Bacillus amyloliquefaciens [3]
8	s G G A T C A C C t C G G A T	Фрагмент ДНК Bifidobacterium infanis [3]
9	s G A C G C G G A tG A C G C	Фрагмент ДНК Haemophilus gallinarum [3]
10	s T C C A A C G A A t C C A A C	Фрагмент ДНК Methylophilus methylotrophus [3]

Оформлення звіту та порядок його подання

Скласти звіт у форматі Word. У звіті повинен бути присутній лістинг програми, приклад виконання програми на тестових даних, згідно з варіантом.

Також потрібно додати до звіту ручну перевірку роботи алгоритму з поясненнями кроків виконання. Результати, отримані за допомогою ручного вирівнювання та за допомогою програми повинні збігатись.

Контрольні запитання та завдання

1) Оптимізувати блоки 1–5 для зменшення кількості операцій.

2) Яка функція штрафу w(k) наведена в алгоритмі прикладу?

3) Яка перевага з трьох можливих:

а) символ – символ;

б) пробіл – символ;

в) символ – пробіл

за однакової ваги закладена в алгоритмі вирівнювання, наведеному в прикладі?

4) Переставити операції у вихідному алгоритмі так, щоб перевагою при виборі оптимального вирівнювання (якщо є декілька варіантів за однакової ваги) було:

а) символ – символ;

б) пробіл – символ;

в) символ – пробіл.

5) Змінити функцію штрафу w(k) на нелінійну в прикладі так, щоб пробіли, що стоять підряд, були більш пріоритетними в порівнянні з тією ж кількістю, але розділених блоками символ – символ.

6) Змінити функцію штрафу на нелінійну в прикладі так, щоб пробіли, розділені блоками символ - символ, були більш пріоритетними в порівнянні з тією ж кількістю, але тих, що стоять підряд.

7) Якою повинна бути функція штрафу в алгоритмі блочного вирівнювання, щоб оптимальне вирівнювання, побудоване за цим алгоритмом співпадало з алгоритмом глобального вирівнювання лабораторної роботи № 1?

8) Як залежить кількість операцій, необхідних для побудови матриць a, b, c блочного вирівнювання двох рядків довжиною m і n по алгоритму, наведеному в прикладі, від їх довжини? Яка причина виникнення відмінності з основним алгоритмом?

9) Які рекурентні формули використовуються для розрахунку елементів масивів a(i, j), b(i, j), c(i, j)?

10) На блоки яких типів можна розкласти кожне вирівнюванняза алгоритмом загальної функції штрафу?

11) Чи можуть блоки довільним чином слідувати один за одним?

12) Для порівняння яких блоків використовуються масиви a(i,j), b(i,j), c(i,j)?

13) Чому нелінійна функція штрафу є більш оптимальною, у порівнянні з алгоритмом глобального вирівнювання, в якому використовується лінійна функція штрафу?