Обладнання

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

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

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

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

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

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

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

1	sCTGTGGTGCTGTGG tGACATCAGCA	Фрагмент ДНК [1]
2	s A G A C C A G A T T T C T G C t T T A G A A C C AC C G	Фрагмент ДНК біка [1]
3	s A A A T G C G T A G A G A T C t G T G G C G A T G T G G	Фрагмент ДНК E.coli [1]
4	s T A G T G T A T T G A C A t A T C A G A T A C	Фрагмент ДНК E.coli [1]
5	s A G T T A G T G T A T T G t T T A G C G G A T C	Фрагмент ДНК фага Р22 [1]
6	s G C T T C C C G A T A A G G t A C T A C CA C CA C	Фрагмент ДНК E.coli [1]
7	s C T C T G C G G G C T T t G A A C G A C C G	Фрагмент ДНК миші [2]
8	s A G G G T C C G G C G C t G A G G T C G A C	Фрагмент ДНК миші [2]
9	s T C T T T G A A T A A A G t C T G C C T A A T	Фрагмент ДНК людини [2]
1	s T G T A T T T A A A T T t G A A C C T T C C	Фрагмент ДНК людини [2]

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Чи однакову кількість елементів містять результуючі вирівнянні послідовності?

4) Яку максимальну кількість елементів можуть містити вирівнянні послідовності, якщо початкові послідовності мають довжини n та m символів?

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

6) Порівняйте кількість операцій, необхідних для вирівнювання двох рядків в залежності від їх довжини з допомогою алгоритму наведеної програми та методом прямого перебору.

7) Як залежить кількості операцій, необхідних для побудови глобального вирівнювання рядків довжин m і n, якщо матриця шляхів вже порахована?

8) Яка функція штрафу використовується для к пробілів, що стоять підряд, у вирівняних рядках?

9) Яка основна ідея одержання вирівнювання рядків в алгоритмі, наведеному в прикладі?

10) Чому дорівнюють значення матриці ваг?

11) Скільки елементів містять масиви p, way для рядків s1 (m), s2 (n)?

12) Які недоліки лінійної функції штрафу для пробілів?

13) Пропрацювати вручну алгоритм побудови вирівнювань на тестових прикладах. Вказати стрілками шлях побудови глобального вирівнювання зі стартової точки матриці ваг.