Jump to content

Устранение тупика

Алгоритм устранения тупика ( DEE ) — метод минимизации функции переменных по дискретному набору независимых . Основная идея заключается в выявлении «тупиков», то есть комбинаций переменных, которые не являются необходимыми для определения глобального минимума , поскольку всегда существует способ заменить такую ​​комбинацию лучшей или эквивалентной. Тогда мы можем воздержаться от дальнейшего поиска таких комбинаций. Следовательно, устранение тупиков является зеркальным отражением динамического программирования , в котором «хорошие» комбинации выявляются и исследуются дальше.

Хотя сам метод является общим, он был разработан и применен в основном для задач прогнозирования и проектирования структур белков . Это тесно связано с понятием доминирования в оптимизации, также известным как заменяемость в задаче удовлетворения ограничений . Исходное описание и доказательство теоремы об исключении тупика можно найти в [1] .

Основные требования

[ редактировать ]

Эффективная реализация DEE требует четырех частей информации:

  1. Хорошо определенный конечный набор дискретных независимых переменных
  2. Предварительно вычисленное числовое значение (считающееся «энергией»), связанное с каждым элементом набора переменных (и, возможно, с их парами, тройками и т. д.).
  3. Критерий или критерии для определения того, когда элемент находится в «тупике», то есть когда он не может быть членом множества решений.
  4. ( Целевая функция называемая «энергетической функцией»), которую необходимо минимизировать.

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

Приложения для предсказания структуры белка

[ редактировать ]

Удаление тупиковых концов эффективно использовалось для прогнозирования структуры боковых цепей на заданной структуре основной цепи белка путем минимизации энергетической функции. . Пространство поиска двугранных углов боковых цепей ограничено дискретным набором ротамеров для каждого положения аминокислоты в белке (который, очевидно, имеет фиксированную длину). Исходное описание DEE включало критерии исключения одиночных ротамеров и пар ротамеров, хотя их можно расширить.

В дальнейшем обсуждении пусть — длина белка и пусть представляют собой ротамер боковая цепь. Поскольку предполагается, что атомы в белках взаимодействуют только посредством потенциалов двух тел , энергию можно записать

Где представляет собой «собственную энергию» конкретного ротамера , и представляет собой «парную энергию» ротамеров .

Также обратите внимание, что (то есть парная энергия между ротамером и самим собой) считается равной нулю и, следовательно, не влияет на суммирование. Эти обозначения упрощают описание парного критерия ниже.

Критерий исключения в одиночном разряде

[ редактировать ]

Если конкретный ротамер или сайдчейн не может дать лучшую энергию, чем другой ротамер одной и той же боковой цепи, то ротамер А можно исключить из дальнейшего рассмотрения, что сокращает пространство поиска. Математически это условие выражается неравенством

где — минимальная (наилучшая) энергия, возможная между ротамером или сайдчейн и любой ротамер X боковой цепи . Сходным образом, - максимальная (худшая) энергия, возможная между ротамером или сайдчейн и любой ротамер X боковой цепи .

Критерий исключения пар

[ редактировать ]

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

Данная пара ротамеров и на позициях и , соответственно, не могут оба находиться в конечном решении (хотя и то, и другое может быть), если существует другая пара и это всегда дает лучшую энергию. Выражаясь математически,

где , и .

Энергетические матрицы

[ редактировать ]

Для больших Хранение матриц предварительно вычисленных энергий может оказаться дорогостоящим. Позволять будет числом аминокислотных позиций, как указано выше, и пусть — количество ротамеров в каждой позиции (обычно, но не обязательно, постоянно во всех позициях). Каждая матрица собственной энергии для данной позиции требует записей, поэтому общее количество собственной энергии, которую нужно сохранить, равно . Матрица энергии каждой пары между двумя позициями и , для дискретные ротамеры в каждой позиции, требует матрица. Это делает общее количество записей в нередуцированной парной матрице . Это можно несколько сократить за счет дополнительной сложности реализации, поскольку парные энергии симметричны, а парная энергия между ротамером и самим собой равна нулю.

Внедрение и эффективность

[ редактировать ]

Два вышеуказанных критерия обычно применяются итеративно до достижения сходимости, определяемой как точка, в которой больше невозможно исключить ротамеры или пары. Поскольку обычно это означает сокращение выборочного пространства на много порядков, простого перебора будет достаточно, чтобы определить минимум в этом урезанном наборе.

Учитывая эту модель, ясно, что алгоритм DEE гарантированно найдет оптимальное решение; то есть это глобальный процесс оптимизации . Поиск одного ротамера масштабируется квадратично по времени с общим количеством ротамеров. Поиск пар масштабируется кубически и является самой медленной частью алгоритма (не считая вычислений энергии). Это значительное улучшение по сравнению с перебором методом грубой силы, который масштабируется как .

Крупномасштабный тест DEE по сравнению с альтернативными методами прогнозирования и проектирования структуры белка показал, что DEE надежно сходится к оптимальному решению для длин белков, для которых он работает за разумный промежуток времени. [2] . Он значительно превосходит рассматриваемые альтернативы, в которых использовались методы, полученные из теории среднего поля , генетических алгоритмов и метода Монте-Карло . Однако другие алгоритмы значительно быстрее, чем DEE, и поэтому могут применяться для решения более крупных и сложных задач; их относительная точность может быть экстраполирована путем сравнения с решением DEE в пределах задач, доступных DEE.

Белковый дизайн

[ редактировать ]

Предыдущее обсуждение неявно предполагало, что ротамеры все они имеют разную ориентацию одной и той же боковой цепи аминокислоты. То есть предполагалось, что последовательность белка фиксирована. Также возможно позволить нескольким сайдчейнам «конкурировать» за позицию. путем включения обоих типов боковых цепей в набор ротамеров для этой позиции. Это позволяет создать новую последовательность на заданном остове белка. короткая белковая складка «цинковых пальцев» . Таким образом была переработана [3] . Однако это значительно увеличивает количество ротамеров на позицию и по-прежнему требует фиксированной длины белка.

Обобщения

[ редактировать ]

Были введены более мощные и более общие критерии, которые повышают как эффективность, так и исключающую способность метода как для приложений прогнозирования, так и для проектирования. Одним из примеров является уточнение критерия исключения одиночных игр, известного как критерий Гольдштейна. [4] , который возникает в результате довольно простых алгебраических манипуляций перед применением минимизации:

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

Подробное обсуждение сложных критериев DEE и контрольных показателей их относительной эффективности можно найти в [5] .

  1. ^ Десмет Дж, де Майер М, Хейз Б, Ластерс И. (1992). Теорема устранения тупика и ее использование для позиционирования боковой цепи белка. Природа , 356 , 539–542. ПМИД   21488406 .
  2. ^ Фойгт Калифорния, Гордон Д.Б., Мэйо С.Л. (2000). Обмен точности на скорость: количественное сравнение алгоритмов поиска при проектировании последовательностей белков. J Мол Биол 299(3):789-803.
  3. ^ Дахият Б.И., Мэй С.Л. (1997). Дизайн белка de novo: полностью автоматизированный выбор последовательности. Наука 278(5335):82-7.
  4. ^ Гольдштейн РФ. (1994). Эффективное устранение ротамеров, применяемое к боковым цепям белков и связанным с ними спиновым стеклам. Биофиз J 66(5):1335-40.
  5. ^ Пирс Н.А., Сприт Дж.А., Десмет Дж., Мэйо С.Л. (2000). Конформационное расщепление: более мощный критерий устранения тупика. J Comput Chem 21: 999-1009.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 8989fe049237d1eaf85bfd5572568737__1662261240
URL1:https://arc.ask3.ru/arc/aa/89/37/8989fe049237d1eaf85bfd5572568737.html
Заголовок, (Title) документа по адресу, URL1:
Dead-end elimination - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)