Введение
Алгоритм минимизации функции на наборе независимых переменных Алгоритм устранения тупика (DEE) - это метод минимизации функции на дискретном наборе независимых переменных. Основная идея заключается в том, чтобы определить "невыгодные" комбинации переменных, которые не являются необходимыми для определения глобального минимума, потому что всегда есть способ заменить такую комбинацию лучшей или эквивалентной. Тогда мы можем воздержаться от дальнейшего поиска таких комбинаций. Таким образом, устранение тупиков - это зеркальное отражение динамического программирования, в котором "хорошие" комбинации идентифицируются и исследуются далее. Хотя сам метод является общим, он был разработан и применен в основном к проблемам прогнозирования и проектирования структур белков. Это тесно связано с понятием доминирования в оптимизации, также известной как замещаемость в проблеме удовлетворения ограничений. Оригинальное описание и доказательство теоремы устранения тупика можно найти в .
The dead end elimination algorithm (DEE) is a method for minimizing a function over a discrete set of independent variables. The basic idea is to identify "dead ends", i. e., combinations of variables that are not necessary to define a global minimum because there is always a way of replacing such combination by a better or equivalent one. Then we can refrain from searching such combinations further. Hence, dead end elimination is a mirror image of dynamic programming, in which "good" combinations are identified and explored further. Although the method itself is general, it has been developed and applied mainly to the problems of predicting and designing the structures of proteins. It closely related to the notion of dominance in optimization also known as substitutability in a Constraint Satisfaction Problem. The original description and proof of the dead end elimination theorem can be found in .
Применение в прогнозировании структуры белка
Элеминация мертвых концов эффективно используется для прогнозирования структуры боковых цепей на заданной структуре белкового хребта путем минимизации энергетической функции. Пространство поиска боковых цепей в диэдрическом углу ограничено дискретным набором ротамеров для каждой позиции аминокислоты в белке (которая, очевидно, имеет фиксированную длину). Первоначальное описание DEE включало критерии для устранения одиночных ротамеров и пар ротамеров, хотя это может быть расширено. В следующем обсуждении давайте будем длиной белка и давайте будем представлять ротамер боковой цепи. Поскольку атомы в белках взаимодействуют только с помощью двух потенциалов тела, энергия может быть записана где представляет собой "самостоятельную энергию" конкретного ротамара, и представляет собой "парную энергию" ротамаров. Также обратите внимание, что (то есть, парная энергия между ротамаром и самим собой) принимается за нуль, и, таким образом, не влияет на суммации. Эта нотация упрощает описание критерия пар ниже.
Where represents the "self energy" of a particular rotamer , and represents the "pair energy" of the rotamers
Also note that (that is, the pair energy between a rotamer and itself) is taken to be zero, and thus does not affect the summations. This notation simplifies the description of the pairs criterion below.
Критерий отбора в одиночных матчах
Если конкретный ротатор боковой цепи не может дать лучшую энергию, чем другой ротатор той же боковой цепи, то ротатор А может быть исключен из дальнейшего рассмотрения, что уменьшает пространство поиска. Математически это условие выражается неравенством где минимальная (лучшая) возможная энергия между ротатором боковой цепи и любым ротатором X боковой цепи Аналогичным образом, максимальная (худшая) возможная энергия между ротатором боковой цепи и любым ротатором X боковой цепи.
where is the minimum (best) energy possible between rotamer of sidechain and any rotamer X of side chain Similarly, is the maximum (worst) energy possible between rotamer of sidechain and any rotamer X of side chain .
Критерий исключения пар
Критерий пар сложнее описать и реализовать, но он добавляет значительную силу устранения. Для краткости мы определяем краткую переменную, которая является внутренней энергией пары ротамеров и в позициях и , соответственно, данная пара ротамеров и в позициях и , соответственно, не может быть в конечном решении (хотя одна или другая может быть), если есть другая пара, и это всегда дает лучшую энергию. Выражается математически, где , и .
A given pair of rotamers and at positions and , respectively, cannot both be in the final solution (although one or the other may be) if there is another pair and that always gives a better energy. Expressed mathematically,
where , and .
Энергетические матрицы
Для больших матриц с заранее вычисленной энергией может быть дорого хранить. Пусть число аминокислотных позиций, как выше, и пусть число ротамеров в каждом положении (это обычно, но не обязательно, постоянное во всех положениях). Каждая матрица энергии для данного положения требует входов, поэтому общее количество энергий для хранения - это Каждая паровая матрица энергии между двумя позициями и , для дискретных ротаторов в каждой позиции требует матрицы. Это делает общее количество записей в матрице несниженной пары. Это можно несколько урезать, за счет дополнительной сложности в реализации, потому что энергии пары симметричны, а энергия пары между ротатором и самим собой равна нулю.
Реализация и эффективность
Вышеуказанные два критерия обычно применяются итеративно до конвергенции, определяемой как точка, в которой больше не может быть устранено ротаторов или пар. Поскольку это обычно сокращение пространства выборки на многие порядки величины, простого перечисления будет достаточно для определения минимума в пределах этого сокращенного набора. Учитывая эту модель, ясно, что алгоритм DEE гарантированно найдет оптимальное решение; то есть это процесс глобальной оптимизации. Поиск одного ротамера масштабируется в квадратном порядке во времени с общим количеством ротамеров. Поиск пары масштабируется кубически и является самой медленной частью алгоритма (кроме расчетов энергии). Это значительно улучшило результаты по сравнению с методом перечисления грубой силы, который масштабируется как крупномасштабный эталонный показатель DEE по сравнению с альтернативными методами прогнозирования и проектирования структуры белка, который находит, что DEE надежно сближается с оптимальным решением для длин белка, для которого он работает в разумное время. Он значительно превосходит рассматриваемые альтернативы, которые включали методы, полученные из теории среднего поля, генетических алгоритмов и метода Монте-Карло. Однако другие алгоритмы значительно быстрее, чем DEE, и поэтому могут применяться к более крупным и сложным проблемам; их относительная точность может быть экстраполирована на основе сравнения с решением DEE в рамках проблем, доступных для DEE.
A large scale benchmark of DEE compared with alternative methods of protein structure prediction and design finds that DEE reliably converges to the optimal solution for protein lengths for which it runs in a reasonable amount of time. It significantly outperforms the alternatives under consideration, which involved techniques derived from mean field theory, genetic algorithms, and the Monte Carlo method. However, the other algorithms are appreciably faster than DEE and thus can be applied to larger and more complex problems; their relative accuracy can be extrapolated from a comparison to the DEE solution within the scope of problems accessible to DEE.
Конструкция белка
В предыдущем обсуждении неявно предполагалось, что ротамеры являются разными ориентациями одной и той же боковой цепи аминокислот. То есть последовательность белка была зафиксирована. Также можно позволить нескольким боковым цепям "соревноваться" за позицию, включив оба типа боковых цепей в набор ротаторов для этой позиции. Это позволяет разработать новую последовательность на заданном белковом основном. Короткий цинковый палец протеина был переделан таким образом. Однако это значительно увеличивает количество ротамеров на одну позицию и по-прежнему требует фиксированной длины белка.
Обобщения
Внедрены более мощные и более общие критерии, которые повышают эффективность и устраняющую способность метода как для прогнозирования, так и для проектирования. Одним из примеров является уточнение критерия исключения одиночных чисел, известного как критерий Голдштейна, который возникает из довольно простой алгебраической манипуляции перед применением минимизации: Таким образом, ротамер может быть устранен, если любой альтернативный ротамер из множества at вносит меньший вклад в общую энергию, чем это является улучшением по сравнению с первоначальным критерием, который требует сравнения наилучшего возможного (то есть наименьшего) энергетического вклада с худшим возможным вкладом от альтернативного ротамера. Обширное обсуждение детальных критериев ДЭО и эталон их относительных показателей можно найти в .
Thus rotamer can be eliminated if any alternative rotamer from the set at contributes less to the total energy than This is an improvement over the original criterion, which requires comparison of the best possible (that is, the smallest) energy contribution from with the worst possible contribution from an alternative rotamer. An extended discussion of elaborate DEE criteria and a benchmark of their relative performance can be found in .