- •Біоінформатика
- •Особливості реалізації
- •Лабораторна робота 1 побудова глобального вирівнювання
- •Обладнання
- •Порядок виконання роботи
- •Тестові приклади
- •Оформлення звіту та порядок його подання
- •Контрольні запитання та завдання
- •Лабораторна робота 2 побудова локального вирівнювання
- •Обладнання
- •Порядок виконання роботи
- •Тестові приклади
- •Оформлення звіту та порядок його подання
- •Контрольні запитання та завдання
- •Лабораторна робота 3 побудова псевдоглобального вирівнювання
- •Реалізація алгоритму
- •Обладнання
- •Порядок виконання роботи
- •Тестові приклади
- •Оформлення звіту та порядок його подання
- •Контрольні запитання та завдання
- •Лабораторна робота 4 загальна функція штрафу
- •Реалізація алгоритму
- •Обладнання
- •Порядок виконання роботи
- •Тестові приклади
- •Оформлення звіту та порядок його подання
- •Контрольні запитання та завдання
- •Лабораторна робота 5 порівняння подібних послідовностей
- •Реалізація алгоритму
- •Обладнання
- •Порядок виконання роботи
- •Тестові приклади
- •Оформлення звіту та порядок його подання
- •Контрольні запитання та завдання
- •Лабораторна робота 6 матриця рам
- •Реалізація алгоритму
- •Обладнання
- •Порядок виконання роботи
- •Тестові приклади
- •Оформлення звіту та порядок його подання
- •Контрольні запитання та завдання
- •Література та посилання
Лабораторна робота 5 порівняння подібних послідовностей
Мета роботи – ознайомитись з поняттям порівняння подібних послідовностей та навчитися писати й використовувати програми для порівняння подібних послідовностей.
Теоретичні відомості
Розглянемо алгоритм швидкого вирівнювання подібних послідовностей (лише для випадку глобального вирівнювання), коли порівнюються послідовності однакової довжини n. В цьому випадку матриця ваг стає квадратною і по головній діагоналі розміщено вирівнювання без пробілів між sit. Якщо таке вирівнювання не оптимальне, то необхідно ввести пробіли для одержання більшої ваги. Пробіли завжди вводяться попарно, один в sі один в t. Вирівнювання все ще ведеться поблизу головної діагоналі.
Основна ідея полягає в тому, що якщо послідовності схожі, найкраще вирівнювання лежить в малому оточенні головної діагоналі. В лабораторній роботі наведено приклад алгоритму для заповнення матриці в горизонтальній (вертикальній) смузі шириною 2k+1 навколо головної діагоналі. Елемент p[n, n] містить максимальну вагу вирівнювання в смузі заданої ширини. Час роботи – O(kn). Відмітимо, що значення поза смугою ширини k не використовуються і відповідно не розраховуються. Для того, щоб визначити, чи лежить позиція (i, j) всередині смуги, використовується проста перевірка:
-k≤ i-j ≤k
Як і в інших алгоритмах динамічного програмування, кожен елемент матриці ваг залежить лише від трьох попередніх значень: сусіднього зліва, зверху та по діагоналі (зверху-зліва).
Після першого проходження алгоритму, якщо одержане значення p[n, n] для фіксованого значення k більше або дорівнює вазі найкращого вирівнювання з k+1 пробілами, то знайдено оптимальне вирівнювання.
Опис алгоритму
Алгоритм швидкого вирівнювання має мету вирівняти схожі послідовності, не будуючи всю матрицю ваг, а лише ті елементи, що лежать близько до головної діагоналі.
Тому, можна зробити спрощення до алгоритму глобального вирівнювання та, по-перше, не виставляти початкові пробіли уздовж усього першого рядка та всієї першої строки. Потрібно проставити перші kелементів у рядку та у строчці.
По-друге, потрібно робити розрахунок лише тих елементів матриці ваг, що лежать поряд з головною діагоналлю, тобто, модуль різниці координат не повинен перевищувати k.
Реалізація алгоритму
#Вводимо послідовності
s1 = input('Введіть першу послідовність: ') #Напрклад 'AGCCAC'
s2 = input('Введіть другупослідовність: ') #Наприклад 'ACCAG'
#Матрицю p (у нашому випадку - matrix) будемо заповнювати дуже малими значеннями, тому що
#неможна виходити за межі головної діагоналі.
MINIMUM = -100
#Позначаємо границі швидкого вирівнювання
k = 2
#Створюємо матрицю
matrix = []
for x inrange(len(s1) + 1): #Заповнюємо її мінімальними значеннями.
stolbets = []
for y inrange(len(s2) + 1):
stolbets.append(MINIMUM)
matrix.append(stolbets)
#Створюємо матрицю шляхів.
way = []
for x inrange(len(s1) + 1): #Заповнюємо її початковими значеннями.
stolbets = []
for y inrange(len(s2) + 1):
stolbets.append(0)
way.append(stolbets)
#Заповнюємо початкові значення для першого стовпчика та першого рядка
for x inrange(k + 1):
matrix[x][0] = x * (-2)
for y inrange(k + 1):
matrix[0][y] = y * (-2)
#Починаємо проходити по елементам головної діагоналі, тобто тим, що не виходять за k елементів від неї.
#Ті, що виходять – ігноруємо.
for y inrange(1, len(s2) + 1):
for x inrange(1, len(s1) + 1):
if x - y <= kand y - x <= k:
levo = matrix[x - 1][y] - 2
verh = matrix[x][y - 1] - 2
if s1[x - 1] == s2[y - 1]:
slogaemoe = 1
else: slogaemoe = -1
diag = matrix[x - 1][y - 1] + slogaemoe #Заповнення ведеться за тими ж правилами, що і в глобальному вирівнюванні.
if levo >= verh and levo >= diag:
matrix[x][y] = levo
way[x][y] = 'l'
if verh >= levo and verh >= diag:
matrix[x][y] = verh
way[x][y] = 'v'
if diag >= levo and diag >= verh:
matrix[x][y] = diag
way[x][y] = 'd'
x = len(s1)
y = len(s2)
res1 = ''
res2 = ''
#Зворотній шлях йде по тому ж принципу, що і в глобальному вирівнюванні.
while x != 0 and y != 0:
if way[x][y] == 'l':
res1 = s1[x - 1] + res1
res2 = '_' + res2
x = x - 1
if way[x][y] == 'v':
res1 = '_' + res1
res2 = s2[y - 1] + res2
y = y - 1
if way[x][y] == 'd':
res1 = s1[x - 1] + res1
res2 = s2[y - 1] + res2
x = x - 1
y = y - 1
#Виводимо результати:
print('Первый результат: ' + res1)
print('Второй результат: ' + res2)
print('Матриця:')
for row in matrix:
print(row)