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

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

Пространственное выравнивание позволяет сравнивать две и более молекулы, для которых известны трехмерные структуры. Два основных метода их получения — рентгеноструктурный анализ и ЯМР-спектроскопия. Для пространственного выравнивания можно также использовать структуры, полученные методами предсказания структуры белка. Пространственные выравнивания особенно важны для анализа данных, полученных методами структурной геномики и протеомики, они также могут использоваться для оценки выравниваний, полученных путём сравнения последовательностей.

Данные, получаемые путём структурного выравнивания Результатом работы программ структурного выравнивания, как правило, является совмещение наборов координат атомов и наименьшее среднеквадратическое отклонение (RMSD) между структурами. Кроме того, могут быть рассчитаны и более сложные параметры, оценивающие структурное сходство, например, . RMSD указывает на степень расхождения выравниваемых структур. Структурное выравнивание может быть затруднено из-за наличия нескольких доменов в структуре выравниваемых белков, так как изменения в относительном расположении этих доменов между двумя структурами могут искусственно изменять значение RMSD. Из структурного выравнивания непосредственно вытекает соответствующее одномерное выравнивание последовательностей, кроме того, на его основании можно рассчитать долю аминокислотных остатков, идентичных между двумя белками.

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

Самый простой способ сравнить две структуры не требует выравнивания самих структур, а использует выравнивание последовательностей. Оно определяет, какие пары аминокислотных остатков сопоставлены друг другу, и затем только они используются для подсчёта RMSD. Наложение структур обычно используется для сравнения нескольких конформаций одного белка (в этом случае даже не нужно выравнивать последовательности) и для оценки качества выравниваний последовательностей, если для них известны структуры. Традиционно при наложении структур используется простой метод наименьших квадратов, в котором оптимальные повороты и трансляции находят через минимизацию суммы квадратов расстояний между всеми структурами в наложении. В недавнее время подобный поиск стал более точным благодаря методам максимального правдоподобия и байесовским методам.

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

Представление структур Для того чтобы сравнивать структуры белков, нужно представить их в пространстве, которое не зависит от координат. Это обычно достигается с помощью матрицы «последовательность против последовательности» или серии матриц, которые включают меры сравнения, относящиеся к фиксированному пространству координат, а не абсолютные расстояния. Очевидным способом подобного представления является матрица расстояний, которая представляет собой двумерную матрицу, содержащую все попарные расстояния между некоторым набором атомов в каждой структуре (например, ). Размерность такой матрицы с увеличением числа одновременно сравниваемых структур растёт. Представив белок в виде крупных частей, таких как элементы вторичной структуры (SSEs) или другие структурные фрагменты, тоже можно получить разумное выравнивание, несмотря на потерю информации от неучтенных расстояний, так как не будет учитываться и шум от них. Таким образом, выбор способа представления белка для облегчения вычислений является критическим для разработки эффективного алгоритма выравнивания.

Вычислительная сложность

Оптимальное решение Было показано, что оптимальное «» белковой последовательности через известную структуру и построение оптимального множественного выравнивания последовательностей являются NP-полными задачами. Однако обычная задача структурного выравнивания не является NP-полной. Строго говоря, оптимальное решение задачи структурного выравнивания белков известно только для некоторых мер сходства белковых структур — например, мер, используемых в задачах предсказания структуры белка GDT_TS и MaxSub. Такие меры могут быть оптимизированы, используя алгоритм, способный максимизировать число атомов в двух белках, которые могут быть совмещены, так как удовлетворяют предустановленному порогу на расстояние между ними. К сожалению, алгоритм оптимального выравнивания непрактичен, так как время его работы зависит не только от длин последовательностей, но и от геометрии выравниваемых белков.

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

Методы Структурное выравнивание используется как при сравнении отдельных структур или их наборов, так и при создании баз данных сравнений «все-против-всех» («all-to-all»), которые отражают различия между каждой парой структур, присутствующих в Protein Data Bank (PDB). Такие базы данных обычно используются для классификации белков по их укладке.

DALI Одним из популярных методов структурного выравнивания является DALI ( — метод с использованием матрицы дистанционных выравниваний). В нём исходные структуры белков разбиваются на гексапептиды и через оценку паттернов контактов между фрагментами рассчитывается матрица расстояний. Элементы вторичной структуры, остатки которых являются соседними в последовательности, оказываются на главной диагонали матрицы; остальные диагонали матрицы отражают пространственные контакты между остатками, которые в последовательности не находятся рядом друг с другом. Если эти диагонали параллельны главной диагонали, то элементы вторичной структуры, которые они представляют, тоже параллельны; если они, напротив, перпендикулярны ей, то их элементы вторичной структуры антипараллельны. Такое представление интенсивно работает с памятью, так как используемая матрица симметрична относительно главной диагонали (и потому избыточна).

Когда матрицы расстояний двух белков имеют одинаковые или похожие элементы примерно на одинаковых позициях, можно сказать, что белки имеют схожую укладку и их элементы вторичной структуры соединены петлями примерно одинаковой длины. Непосредственный процесс выравнивания DALI заключается в поиске схожестей матриц, построенных для двух белков; обычно это осуществляется с помощью серии перекрывающихся подматриц размера 6 × 6. Соответствия подматриц потом пересобираются в конечное выравнивание с помощью стандартного алгоритма максимизации счёта. Оригинальная версия DALI использует симуляцию Монте-Карло для максимизации значения пространственной схожести, являющегося функцией от расстояний между предполагаемыми соответствующими атомами. В частности, вес более отдалённых атомов внутри соответствующих элементов структуры экспоненциально занижается, чтобы уменьшить шум, вызванный подвижностью петель, искривлением спиралей и другими мелкими вариациями структур. Поскольку DALI основан на матрице расстояний типа «все-против-всех», метод может учитывать расположение элементов структур в различном порядке в двух сравниваемых последовательностях.

Метод DALI был использован для создания базы данных (), в которой все известные структуры белков были попарно выровнены для определения их пространственного родства и классификации укладок.

DaliLite является скачиваемой программой, использующей алгоритм DALI.

Комбинаторное расширение Метод комбинаторного расширения () похож на DALI тем, что тоже разбивает каждую структуру на ряд фрагментов, которые затем пытается заново собрать в полное выравнивание. Серия попарных сочетаний фрагментов, называемых AFP ( — пары выровненных фрагментов), используется для задания матрицы сходства, через которую прокладывается оптимальный путь для определения конечного выравнивания. Только те AFP, которые удовлетворяют заданным критериям локального сходства, включаются в матрицу, что сокращает необходимое пространство поиска и увеличивает эффективность. Возможны разные меры сходства; в первоначальном виде метод CE использовал только структурные совмещения и расстояния между остатками, но со временем был расширен для использования локальных свойств, таких как вторичная структура, доступность растворителя, паттерны водородных связей и двугранные углы.

Путь, соответствующий выравниванию, рассчитывается как оптимальный путь через матрицу сходства с помощью линейного прохода через последовательности, расширяя выравнивание следующей возможной AFP с высоким счётом. Начальная AFP, инициирующая выравнивание, может быть выбрана в любой точке матрицы последовательностей. Далее происходит расширение на AFP, которая удовлетворяет заданному критерию на расстояние, ограничивающему размер гэпов (разрывов) в выравнивании. Размер каждой AFP и наибольшая длина гэпа являются необходимыми входными параметрами, но обычно устанавливаются равными эмпирически определённым значениям 8 и 30 соответственно. Подобно DALI или SSAP, CE использовался для создания базы данных классификации укладок на основе известных пространственных структур белков из PDB. Недавно PDB выпустил обновлённую версию CE, которая может определять циклические перестановки в структуре белков.

SSAP