Устранение тупика
Алгоритм устранения тупика ( DEE ) — метод минимизации функции переменных по дискретному набору независимых . Основная идея заключается в выявлении «тупиков», то есть комбинаций переменных, которые не являются необходимыми для определения глобального минимума , поскольку всегда существует способ заменить такую комбинацию лучшей или эквивалентной. Тогда мы можем воздержаться от дальнейшего поиска таких комбинаций. Следовательно, устранение тупиков является зеркальным отражением динамического программирования , в котором «хорошие» комбинации выявляются и исследуются дальше.
Хотя сам метод является общим, он был разработан и применен в основном для задач прогнозирования и проектирования структур белков . Это тесно связано с понятием доминирования в оптимизации, также известным как заменяемость в задаче удовлетворения ограничений . Исходное описание и доказательство теоремы об исключении тупика можно найти в [1] .
Основные требования
[ редактировать ]Эффективная реализация DEE требует четырех частей информации:
- Хорошо определенный конечный набор дискретных независимых переменных
- Предварительно вычисленное числовое значение (считающееся «энергией»), связанное с каждым элементом набора переменных (и, возможно, с их парами, тройками и т. д.).
- Критерий или критерии для определения того, когда элемент находится в «тупике», то есть когда он не может быть членом множества решений.
- ( Целевая функция называемая «энергетической функцией»), которую необходимо минимизировать.
Обратите внимание, что критерии можно легко поменять местами, чтобы определить максимум данной функции.
Приложения для предсказания структуры белка
[ редактировать ]Удаление тупиковых концов эффективно использовалось для прогнозирования структуры боковых цепей на заданной структуре основной цепи белка путем минимизации энергетической функции. . Пространство поиска двугранных углов боковых цепей ограничено дискретным набором ротамеров для каждого положения аминокислоты в белке (который, очевидно, имеет фиксированную длину). Исходное описание DEE включало критерии исключения одиночных ротамеров и пар ротамеров, хотя их можно расширить.
В дальнейшем обсуждении пусть — длина белка и пусть представляют собой ротамер боковая цепь. Поскольку предполагается, что атомы в белках взаимодействуют только посредством потенциалов двух тел , энергию можно записать
Где представляет собой «собственную энергию» конкретного ротамера , и представляет собой «парную энергию» ротамеров .
Также обратите внимание, что (то есть парная энергия между ротамером и самим собой) считается равной нулю и, следовательно, не влияет на суммирование. Эти обозначения упрощают описание парного критерия ниже.
Критерий исключения в одиночном разряде
[ редактировать ]Если конкретный ротамер или сайдчейн не может дать лучшую энергию, чем другой ротамер одной и той же боковой цепи, то ротамер А можно исключить из дальнейшего рассмотрения, что сокращает пространство поиска. Математически это условие выражается неравенством
где — минимальная (наилучшая) энергия, возможная между ротамером или сайдчейн и любой ротамер X боковой цепи . Сходным образом, - максимальная (худшая) энергия, возможная между ротамером или сайдчейн и любой ротамер X боковой цепи .
Критерий исключения пар
[ редактировать ]Парный критерий сложнее описать и реализовать, но он добавляет значительную исключающую способность. Для краткости мы определим сокращенную переменную это собственная энергия пары ротамеров и на позициях и , соответственно
Данная пара ротамеров и на позициях и , соответственно, не могут оба находиться в конечном решении (хотя и то, и другое может быть), если существует другая пара и это всегда дает лучшую энергию. Выражаясь математически,
где , и .
Энергетические матрицы
[ редактировать ]Для больших Хранение матриц предварительно вычисленных энергий может оказаться дорогостоящим. Позволять будет числом аминокислотных позиций, как указано выше, и пусть — количество ротамеров в каждой позиции (обычно, но не обязательно, постоянно во всех позициях). Каждая матрица собственной энергии для данной позиции требует записей, поэтому общее количество собственной энергии, которую нужно сохранить, равно . Матрица энергии каждой пары между двумя позициями и , для дискретные ротамеры в каждой позиции, требует матрица. Это делает общее количество записей в нередуцированной парной матрице . Это можно несколько сократить за счет дополнительной сложности реализации, поскольку парные энергии симметричны, а парная энергия между ротамером и самим собой равна нулю.
Внедрение и эффективность
[ редактировать ]Два вышеуказанных критерия обычно применяются итеративно до достижения сходимости, определяемой как точка, в которой больше невозможно исключить ротамеры или пары. Поскольку обычно это означает сокращение выборочного пространства на много порядков, простого перебора будет достаточно, чтобы определить минимум в этом урезанном наборе.
Учитывая эту модель, ясно, что алгоритм DEE гарантированно найдет оптимальное решение; то есть это глобальный процесс оптимизации . Поиск одного ротамера масштабируется квадратично по времени с общим количеством ротамеров. Поиск пар масштабируется кубически и является самой медленной частью алгоритма (не считая вычислений энергии). Это значительное улучшение по сравнению с перебором методом грубой силы, который масштабируется как .
Крупномасштабный тест DEE по сравнению с альтернативными методами прогнозирования и проектирования структуры белка показал, что DEE надежно сходится к оптимальному решению для длин белков, для которых он работает за разумный промежуток времени. [2] . Он значительно превосходит рассматриваемые альтернативы, в которых использовались методы, полученные из теории среднего поля , генетических алгоритмов и метода Монте-Карло . Однако другие алгоритмы значительно быстрее, чем DEE, и поэтому могут применяться для решения более крупных и сложных задач; их относительная точность может быть экстраполирована путем сравнения с решением DEE в пределах задач, доступных DEE.
Белковый дизайн
[ редактировать ]Предыдущее обсуждение неявно предполагало, что ротамеры все они имеют разную ориентацию одной и той же боковой цепи аминокислоты. То есть предполагалось, что последовательность белка фиксирована. Также возможно позволить нескольким сайдчейнам «конкурировать» за позицию. путем включения обоих типов боковых цепей в набор ротамеров для этой позиции. Это позволяет создать новую последовательность на заданном остове белка. короткая белковая складка «цинковых пальцев» . Таким образом была переработана [3] . Однако это значительно увеличивает количество ротамеров на позицию и по-прежнему требует фиксированной длины белка.
Обобщения
[ редактировать ]Были введены более мощные и более общие критерии, которые повышают как эффективность, так и исключающую способность метода как для приложений прогнозирования, так и для проектирования. Одним из примеров является уточнение критерия исключения одиночных игр, известного как критерий Гольдштейна. [4] , который возникает в результате довольно простых алгебраических манипуляций перед применением минимизации:
Таким образом, ротамер можно исключить, если какой-либо альтернативный ротамер из набора по адресу вносит меньший вклад в общую энергию, чем . Это улучшение по сравнению с исходным критерием, который требует сравнения наилучшего возможного (то есть наименьшего) энергетического вклада от с наихудшим вкладом альтернативного ротамера.
Подробное обсуждение сложных критериев DEE и контрольных показателей их относительной эффективности можно найти в [5] .
Ссылки
[ редактировать ]- ^ Десмет Дж, де Майер М, Хейз Б, Ластерс И. (1992). Теорема устранения тупика и ее использование для позиционирования боковой цепи белка. Природа , 356 , 539–542. ПМИД 21488406 .
- ^ Фойгт Калифорния, Гордон Д.Б., Мэйо С.Л. (2000). Обмен точности на скорость: количественное сравнение алгоритмов поиска при проектировании последовательностей белков. J Мол Биол 299(3):789-803.
- ^ Дахият Б.И., Мэй С.Л. (1997). Дизайн белка de novo: полностью автоматизированный выбор последовательности. Наука 278(5335):82-7.
- ^ Гольдштейн РФ. (1994). Эффективное устранение ротамеров, применяемое к боковым цепям белков и связанным с ними спиновым стеклам. Биофиз J 66(5):1335-40.
- ^ Пирс Н.А., Сприт Дж.А., Десмет Дж., Мэйо С.Л. (2000). Конформационное расщепление: более мощный критерий устранения тупика. J Comput Chem 21: 999-1009.