Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ФБТ БИ 2курс / Методичка.docx
Скачиваний:
28
Добавлен:
10.04.2018
Размер:
175.97 Кб
Скачать

Лабораторна робота 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)

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