7.2: Вирівнювання грубої сили

Один (поганий) підхід до вирівнювання послідовностей полягає у вирівнюванні двох послідовностей усіма можливими способами, оцінка вирівнювання за передбачуваною системою балів та визначення найвищого вирівнювання балів. Проблема цього підходу грубої сили полягає в тому, що кількість можливих вирівнювань зростає експоненціально з довжиною послідовності; а для послідовностей розумної довжини обчислення вже неможливо. Наприклад, кількість способів вирівнювання двох послідовностей по 50 символів кожна - досить невелика проблема вирівнювання - це приблизно$1.5 \times 10^{37}$, вже дивно велика кількість. Інформативно підрахувати кількість можливих вирівнювань між двома послідовностями, оскільки подібний алгоритм використовується для вирівнювання послідовностей.

Припустимо, ми хочемо вирівняти дві послідовності. Зазори в будь-якій послідовності допускаються, але зазор не може бути вирівняний з зазором. Для ілюстрації ми демонструємо три способи вирівнювання першого символу алфавіту верхнього регістру та алфавіту нижнього регістру:

і п'ять способів, за допомогою яких перші два символи алфавіту у верхньому регістрі можуть вирівнюватися з першим символом алфавіту нижнього регістру:

Відношення рекурсії для загальної кількості можливих вирівнювання послідовності$i$ символів з послідовністю$j$ символів може бути виведено, враховуючи вирівнювання останнього символу. Є три можливості, які ми проілюструємо,$i$ припускаючи, що символ$\mathrm{F}$ «»,$j$ а символ - «$\mathrm{d}$»:

(1)$i-1$ символи першої послідовності вже вирівняні з$j-1$ символами другої послідовності, а$i$ й символ першої послідовності точно вирівнюється з$j$ символом другої послідовності:

(2)$i-1$ символи першої послідовності вирівнюються з$j$ символами другої послідовності, а$i$ й символ першої послідовності вирівнюється з проміжком у другій послідовності

(3)$i$ символи першої послідовності вирівнюються з$j-1$ символами другої послідовності, а пробіл у першій послідовності вирівнюється з$j$ символом другої послідовності iil

$\cdots d$

Якщо$C(i, j)$ кількість способів вирівняти послідовність$i$ символів з послідовністю$j$ символів, то, з нашого підрахунку,

$$C(i, j)=C(i-1, j-1)+C(i-1, j)+C(i, j-1) \nonumber$$

Цей рекурсійний зв'язок вимагає граничних умов. Оскільки існує лише один спосіб вирівняти послідовність$i>0$ символів із нульовою послідовністю символів (тобто$i$ символів проти$i$ прогалин), граничні умови є$C(0, j)=C(i, 0)=1$ для всіх$i, j>0$ Ми також можемо додати додаткові гранична умова$C(0,0)=1$, отримана з відомого результату$C(1,1)=3$.

Використовуючи рекурсійне відношення (7.1), ми можемо побудувати наступну динамічну матрицю для підрахунку кількості способів вирівнювання двох п'ятисимвольних послідовностей$a_{1} a_{2} a_{3} a_{4} a_{5}$ і$b_{1} b_{2} b_{3} b_{4} b_{5}$:

$\begin{array}{ccccccc} & - & b_{1} & b_{2} & b_{3} & b_{4} & b_{5} \\[4pt] - & 1 & 1 & 1 & 1 & 1 & 1 \\[4pt] a_{1} & 1 & 3 & 5 & 7 & 9 & 11 \\[4pt] a_{2} & 1 & 5 & 13 & 25 & 41 & 61 \\[4pt] a_{3} & 1 & 7 & 25 & 63 & 129 & 231 \\[4pt] a_{4} & 1 & 9 & 41 & 129 & 321 & 681 \\[4pt] a_{5} & 1 & 11 & 61 & 231 & 681 & 1683\end{array}$

Розмір цієї динамічної матриці є$6 \times 6$, і для зручності ми маркуємо рядки і стовпці, починаючи з нуля (тобто рядок 0, рядок$1, \ldots$, рядок 5). Ця матриця була побудована шляхом спочатку запису$-a_{1} a_{2} a_{3} a_{4} a_{5}$ зліва від матриці і$-b_{1} b_{2} b_{3} b_{4} b_{5}$ над матрицею, потім заповнення одиниць через нульовий рядок і вниз по нульовому стовпчику, щоб задовольнити граничні умови, і, нарешті, застосовуючи рекурсивне відношення безпосередньо, йдучи поперек першого рядка зліва направо, другий рядок зліва направо і т.д. щоб продемонструвати заповнення матриці, ми маємо поперек першого рядка:$1+1+1=3,1+1+3=5,1+1+5=7$, etc, і через другий рядок:$1+3+1=5,3+5+5=13,5+7+13=25$, і т.д., Нарешті, останній введений елемент дає кількість способів вирівнювання дві п'ять послідовностей символів: 1683, вже надзвичайно велика кількість.

Можна аналітично розв'язати рекурсійне відношення (7.1) для$C(i, j)$ використання генеруючих функцій. Хоча метод вирішення цікавий - і насправді мені показав студент-підсумковий аналітичний результат безладний і ми його тут опускаємо. Загалом, обчислення$C(i, j)$ найкраще проводити чисельно шляхом побудови динамічної матриці.