Возвращаясь к задаче распознавания наиболее стабильной
«вторичной» структуры РНК, отметим следующие обстоятельства, характерные для
многих важных задач биоалгоритмики:
§
в описанной выше модели правильнее считать не
количество связей, а их суммарную энергию, энергия каждой возможной пары
считается известной. С алгоритмической точки зрения задача практически не
меняется;
§
модель, положенная в основу описанной выше задачи,
- упрощенная и во многих случаях не согласуется с экспериментом. Полезно
учитывать и вклад нуклеотидов, не участвующих в образовании водородных связей.
Ограничения на множество допустимых наборов связей, принятые в задаче (а),
слишком строгие. Различные формальные постановки задач, лучше отражающие
биологическую реальность, приводят к существенному усложнению алгоритма;
§
в реальности молекула РНК может принимать не ту
структуру, которой мы приписали оптимальную энергию, а несколько иную,
например, из-за того, что мы не знаем точных значений энергетических
параметров. Поэтому полезно не искать одну «оптимальную» структуру, а
проанализировать все возможные структуры и оценить вероятность образования
каждой отдельной связи («статистический вес» связи). Это также можно решить
методом динамического программирования.
§
многие авторы пытаются выяснить вторичную структуру
РНК, не сводя ее к какой-либо алгоритмической оптимизационной задаче, а путем
моделирования реального процесса «сворачивания» молекулы РНК (т. е.
установления и исчезновения водородных связей).
Специфика биоалгоритмики, однако, проявляется не только в
задачах, которые «по определению» не могли встретиться вне анализа
биологических последовательностей. Показательна самая старая и, наверное, самая
популярная задача анализа биологических последовательностей - их выравнивание. Выравнять
две последовательности - это изобразить их друг над другом, вставляя в обе
пробелы так, чтобы сделать их длины равными. Вот, например, как можно
выровнять слова ПОДБЕРЕЗОВИК и ПОДОСИНОВИК (cм. врезку).
Такой способ изображения последовательностей широко
распространен в молекулярной биологии. Предполагается, что выравнивание
отражает эволюционную историю, то есть стоящие друг под другом символы
соответствуют одному и тому же символу последовательности-предка. К сожалению,
мы не знаем, как именно шла эволюция последовательностей. Поэтому в качестве
«правильного» обычно выбирается выравнивание, оптимальное относительно
некоторой функции качества. Но как мы можем контролировать правильность выбора
этой функции? Есть ли у нас (пусть приблизительные) «эталоны»? К счастью, да. В
качестве эталонных можно взять выравнивания, соответствующие наилучшему
возможному совмещению их пространственных структур (такие структуры известны
для нескольких сотен белков). Это связано с тем, что функционирование белка в
клетке определяется прежде всего его пространственной структурой и можно
ожидать, что аминокислоты, лежащие в сходных местах трехмерной структуры,
соответствуют одним и тем же аминокислотам предкового белка.
В «добиологическом» анализе последовательностей (например, при
сравнении файлов) использовалось понятие редактирующего расстояния. При
этом фиксируется набор редактирующих операций (например, замена символа,
вставка символа и удаление символа) и для каждой операции фиксируется цена.
Тогда каждое выравнивание получает свою цену, определяемую как сумма цен
отдельных операций.
Лучшим считается то, которое имеет наименьшую цену. Например,
при цене замены 1 и цене вставки/удаления 3, лучшими в примере во врезке 2
будут третье и четвертое выравнивания, а при цене замены 10 и той же цене
вставки/удаления, лучшим будет пятое.
Довольно скоро выяснилось, что для выравнивания биологических
последовательностей в эту естественную схему необходимо внести ряд важных
изменений. Дело в том, что разные аминокислоты различны по-разному. Например,
аланин и валин очень похожи по своим свойствам (и цена замены аланина на валин
должна быть небольшой), и они оба совершенно не похожи на триптофан. Более
того, даже одинаковые аминокислоты «одинаковы по-разному». Так, триптофан -
редок, и сопоставление двух триптофанов более ценно, чем сопоставление весьма
распространенных аланинов.