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

Last updated
Save as PDF

Page ID: 66628

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Один (поганий) підхід до вирівнювання послідовностей полягає у вирівнюванні двох послідовностей усіма можливими способами, оцінка вирівнювання за передбачуваною системою балів та визначення найвищого вирівнювання балів. Проблема цього підходу грубої сили полягає в тому, що кількість можливих вирівнювань зростає експоненціально з довжиною послідовності; а для послідовностей розумної довжини обчислення вже неможливо. Наприклад, кількість способів вирівнювання двох послідовностей по 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)\) найкраще проводити чисельно шляхом побудови динамічної матриці.