MEME

Multiple EM for Motif Elicitation (MEME) — алгоритм и одноимённый инструмент, являющийся реализацией алгоритма, для поиска мотивов в биологических последовательностях белков и ДНК. Алгоритм основан на многократном применении метода максимального правдоподобия. Под мотивом понимается короткая последовательность нуклеотидов или аминокислот, общая для некоторого набора последовательностей.

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

История

Алгоритм MEME был разработан в 1994 году Тимоти Бейли и Чарльзом Элканом. Он является усилением метода максимального правдоподобия для поиска мотивов, который был опубликован в 1990 году авторами Lawrence и Reilly. Оригинальный метод позволял найти только один мотив в наборе последовательностей, причём этот мотив являлся локально оптимальным, так как алгоритм сильно зависит от выбора стартовых параметров. Корректность его работы также сильно зависела от уровня шума в рассматриваемых последовательностях. Метод MEME позволил обойти эти недостатки. В 1996 году был создан вебсервер, содержащий реализацию MEME, которым за период с 2000 по 2006 год воспользовалось около 800 уникальных посетителей. А в 2009 году был представлен пакет MEME Suite, содержащий в себе не только реализацию MEME, но и многих других сопутствующих программ. Всего над созданием MEME Suite работали: Тимоти Бейли, Уильям Стэффорд Нобель, вклад в проект внесли также Чарльз Элкан и Майкл Грибсков. По состоянию на 2017 год MEME Suite поддерживается грантом NIH, а вебсервер также получает помощь от Google и Amazon.

Постановка задачи

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

Подготовительный этап

Подготовка последовательностей

Не в любом наборе последовательностей возможно обнаружить общий мотив, поэтому для корректной работы алгоритма необходимо внимательно выбрать и подготовить последовательности: общий мотив должен быть ожидаем в этом наборе (например известно, что последовательности связываются с одним транскрипционным фактором), и последовательности должны быть настолько короткие, насколько это возможно (в идеале <1000 нуклеотидов).

Выбор входных параметров

По умолчанию выдача MEME содержит не более трёх мотивов длины от 6 до 50, найденных как на прямой, так и на обратной цепи входных последовательностей. Если известен биологический смысл объектов поиска, то можно предположить и задать количество и длину мотивов, которые ожидаются в этом наборе последовательностей. Это улучшит качество предсказания в случае, если мотив не подходит под параметры по умолчанию.

Алгоритм

EM-алгоритм для поиска последовательностей

На вход EM-алгоритму подаётся:

• набор последовательностей, принадлежащих алфавиту $L$;
• длина предполагаемого мотива $W$.

Алгоритм возвращает возможную модель найденного мотива.

На каждом шаге алгоритма мотив определяется позиционно-весовой матрицей (ПВМ) размера $|L|\times W$, где $|L|$ — размер алфавита. В каждой ячейке ПВМ стоит вес $p_{lc}$, зависящий от вероятности появления буквы $l$ в колонке $c$, где $1\le c\le W$. Эти значения пересчитываются в ходе каждой итерации алгоритма.

Так как изначально неизвестно, где именно в последовательностях находится мотив, на каждом шаге алгоритма вычисляются значения матрицы $Z$, где элемент матрицы $z_{ij}$ — правдоподобие того, что мотив начинается в последовательности $i$ с позиции $j$.

Таким образом, алгоритм состоит из следующей последовательности шагов:

1. Берется начальная ПВМ мотива. Она может быть задана или выбирается случайно.
2. По имеющимся значениям $p_{lc}$ПВМ для каждой позиции в каждой последовательности вычисляются значения матрицы $Z$ с помощью логарифма функции правдоподобия:$$\log (likelihood)=N\sum _{j=1}^W\sum _{l\in L}{f}_{lj}\log (p_{lj})+N(K-W)\sum _{l\in L}{f}_{l0}\log (p_{l0})+N\log (\frac{1}{K-W+1}),$$где $N$ — количество входных последовательностей, $K$ — длина входных последовательностей, $W$ — длина мотива, $L$ — алфавит, $p_{lj}$ — вероятность появления буквы $l$ в позиции $j$ мотива, $p_{l0}$ — вероятность появления буквы $l$ в любой позиции, $f_{lj}$ — наблюдаемая частота буквы $l$ в позиции $j$ мотива, $f_{l0}$ — наблюдаемая частота появления буквы $l$ в любой позиции.
3. Для каждой последовательности выбирается максимум функции правдоподобия из матрицы $Z$ и определяется позиция в последовательности, соответствующая этому максимуму. По соответствующим позициям строится выравнивание, вычисляются новые значения ПВМ по встречаемости букв в искомых колонках мотива.
4. Пункты 2. и 3. повторяются, пока изменения значений ПВМ не станут меньше изначально заданного порога.

Вычисление наилучших входных параметров для алгоритма МЕМЕ

Для улучшения результата EM-алгоритма необходимо правильно выбрать набор стартовых параметров. Для этого есть несколько способов:

1. Запустить алгоритм с различными возможными произвольными входными параметрами, а затем выбрать те, для которых значение функции правдоподобия будет наибольшим. Такой подход улучшает качество предсказания, но не гаратирует лучший результат.
2. Использовать метод подпоследовательностей.

Метод подпоследовательностей основан на том, что искомый мотив должен соответствовать какой-то подпоследовательности длины $W$ в исходных данных. Для каждой такой подпоследовательности строятся ПВМ, с которых и стартует каждый запуск алгоритма EM. Наибольшее значение функции правдоподобия среди всех запусков алгоритма будет глобальным максимумом и даст искомый мотив. Именно этот принцип лимитирует поиск мотивов с гэпами.

По заданной подпоследовательности построить ПВМ можно различными способами. Алгоритм МЕМЕ использует следующий: частота буквы, соответствующей букве в подпоследовательности, принимается за $0<X<1$, лучше всего алгоритм работает для $0,4\le X\le 0,8$. А вероятности для всех остальных букв принимаются за $\frac{1-X}{|L|-1}$.

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

Алгоритм МЕМЕ

Алгоритм МЕМЕ основан на многократном применении ЕМ-алгоритма для поиска мотива в последовательностях. На вход алгоритму МЕМЕ подаётся:

• набор последовательностей, принадлежащих алфавиту $L$;
• длина предполагаемого мотива $W$;
• ожидаемое количество копий мотива;
• количество различных мотивов.

Алгоритм ЕМ модифицируется до следующего:

1. Выбираются начальные параметры методом подпоследовательностей.
2. Для каждого набора входных параметров осуществляется одна итерация ЕМ-алгоритма. Выбирается наибольшее значение функции правдоподобия из всех запусков.
3. Полученный мотив сохраняется и удаляется из входных последовательностей для поиска следующих.
4. Пункты 1., 2. и 3. повторяются для поиска заданного количества мотивов.

Обнаруженные мотивы на выходе программы подаются в виде LOGO.

Время работы алгоритма

Алгоритм МЕМЕ поиска мотива длины $W$ совершает $k*W*n^2$ шагов, где $k$ — неизвестная константа (между 10 и 100), $n$ — это общее количество букв заданного алфавита во входных последовательностях. То есть сложность алгоритма оказывается $O(W*n^2)$.

Достоинства

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

Недостатки

Алгоритмом MEME плохо распознаются мотивы в длинных последовательностях, кроме того большая длина последовательностей сильно увеличивают время работы алгоритма. Также в алгоритме MEME делается важное базовое предположение о равновероятности появления мотива в любой части последовательности. Такой подход не подходит о для поиска мотива в последовательностях РНК, так как они образуют вторичные и третичные структуры, что делает появление мотива более или менее вероятным в зависимости от структуры. Алгоритм не позволяет найти мотивы с гэпами, так как сама постановка задачи алгоритма не предполагает их поиск.

Реализация алгоритма

На основе данного алгоритма реализован инструмент MEME Suite, доступный в веб-версии и для ПК, по состоянию на 2017 год он поддерживается и обновляется.