Задача

Словари в Интернете становятся все более удобными: часто бывает проще открыть сетевой словарь по закладке, чем снимать бумажный словарь с полки. К тому же многие электронные словари предоставляют возможности, отсутствующие в бу- мажных словарях: если вы ищете определение и введете слово, отсутствующее в словаре (например, ocurrance), словарь поинтересуется: «Возможно, вы имели в виду occurrence?» Как он это делает? Он действительно знает, что происходит у вас в голове?

Отложим второй вопрос до другой книги, а пока поразмыслим над первым. Чтобы решить, что вы могли иметь в виду, наиболее естественно провести в словаре поиск слова, наиболее «похожего» на введенное. Для этого нужно ответить на во- прос: как определить сходство между двумя словами или строками?

Интуитивно понятно, что «ocurrance» и «occurrence» похожи, потому что для совпадения этих двух слов достаточно добавить c в первое слово и заменить a на e. Так как ни одно из этих изменений не кажется слишком значительным, можно сделать вывод о том, что между этими двумя словами существует серьезное сход- ство. Иначе говоря, эти два слова можно выстроить параллельно, буква за буквой:

o-currance

occurrence

Дефис (-) обозначает разрыв, который нужно добавить в первое слово для со- вмещения его со вторым. Более того, расположение не идеально, поскольку буква e стоит напротив a.

Нужно построить модель, в которой сходство оценивается по количеству раз- рывов и несовпадений, возникающих при параллельном размещении двух слов. Конечно, слова можно разместить многими разными способами, например:

o-curr-ance

occurre-nce

с тремя разрывами и без несовпадений. Что лучше: один разрыв и одно несовпаде- ние или три разрыва без несовпадений?

Обсуждение упрощалось тем, что мы приблизительно представляли, как долж- но выглядеть соответствие. Если две строки не похожи на английскую слова (на- пример, abbbaabbbbaab и ababaaabbbbbab), решить, можно их выстроить параллель- но или нет, становится сложнее:

abbbaa--bbbbaab

ababaaabbbbba-b

Электронные словари и системы проверки орфографии — не самые требо- вательные приложения такого типа. Оказывается, определение сходства между строками является одной из основных вычислительных задач, которые приходится решать в наши дни специалистам по молекулярной биологии.

Строки встречаются в биологии абсолютно естественно: геном организма (пол- ный набор его генетического материала) делится на гигантские линейные моле- кулы ДНК, называемые хромосомами, каждая из которых может рассматриваться как одномерное химическое устройство хранения информации. Более того, можно вполне адекватно представить себе хромосому как огромную ленту, на которой записана строка из символов алфавита {A, C, G, T}. В этой строке закодированы инструкции по построению белковых молекул; используя химический механизм для чтения частей хромосомы, клетка может строить белки, которые, в свою оче- редь, управляют ее метаболизмом.

Почему сходству отводится важная роль в этой картине? В первом приближе- нии последовательность символов в геноме организма может рассматриваться как определение свойств организма.

Предположим, имеются два штамма бактерий X и Y, между которыми существует тесная эволюционная связь. Также допустим, что нам удалось определить, что некоторая подстрока в ДНК X кодирует некоторую разновидность токсина. Если удастся обнаружить очень «похожую» подстроку в ДНК Y, еще до проведения каких-либо экспериментов можно будет выдвинуть гипотезу, что эта часть ДНК Y кодирует аналогичный токсин. Подобное при- менение вычислений для принятия решений о биологических экспериментах стало одной из характерных особенностей современной вычислительной биологии.

Итак, мы приходим к вопросу, который был задан изначально применительно к вводу неправильных слов в электронный словарь: как определить концепцию сходства между двумя строками?

В начале 1970-х годов молекулярные биологи Нидлман и Вунш предложили определение сходства, которое практически в неизменном виде стало стандартным определением, используемым в наши дни. Его положение как стандарта подкре- плялось простотой и интуитивной привлекательностью, а также тем фактом, что оно было независимо открыто несколькими учеными примерно в одно время. Кроме того, к определению сходства прилагался эффективный алгоритм дина- мического программирования для его вычисления. Таким образом, парадигма динамического программирования была независимо открыта биологами примерно через 20 лет после того, как она была впервые сформулирована математиками и специалистами по информатике.

В основу определения заложены соображения, изложенные выше, и особенно концепция «выстраивания в линию» двух строк. Допустим, имеются две строки X и Y; строкаX содержит последовательность символов x1,x2, ..., х , а строка Y — после- довательность символов y1, y2, ..., yn. Рассмотрим множества {1, 2, ..., m} и {1, 2, ..., n}, представляющие разные позиции в строках X и Y, и рассмотрим паросочетание этих множеств (напомним, что паросочетанием называется множество упорядоченных пар, обладающее тем свойством, что каждый элемент входит не более чем в одну пару). ПаросочетаниеMэтих двух множеств называется выравниванием при отсут- ствии «пересекающихся» пар: если (i, j), (i', j') M и i < i', то j < j'. На интуитивном уровне выравнивание предоставляет способ параллельного расположения двух строк: оно сообщает, какие пары позиций будут находиться друг напротив друга. Например,

stop-

-tops

соответствует выравниванию {(2, 1), (3, 2), (4, 3)}.

Наше определение сходства будет основано на нахождении оптимального вы- равнивания между X и Y по следующему критерию. Предположим, M — заданное выравнивание между X и Y.

♦ Во-первых, должен существовать параметр δ > 0, определяющий штраф за разрыв. Для каждой позиции X или Y, не имеющей пары в M (то есть разрыва), вводится штраф δ.

♦ Во-вторых, для каждой пары букв р, q в нашем алфавите существует штраф за несоответствие apq за совмещение р с q. Таким образом, для всех (i, j)

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.