MEME

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

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

История

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

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

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

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

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

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

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

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

Алгоритм

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

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

• набор последовательностей, принадлежащих алфавиту ${\displaystyle L}$;
• длина предполагаемого мотива ${\displaystyle W}$^[3].

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

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

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

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

1. Берется начальная ПВМ мотива. Она может быть задана или выбирается случайно.
2. По имеющимся значениям ${\displaystyle p_{lc}}$ПВМ для каждой позиции в каждой последовательности вычисляются значения матрицы ${\displaystyle Z}$ с помощью логарифма функции правдоподобия:
   $${\displaystyle \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}}),}$$

   
   где ${\displaystyle N}$ — количество входных последовательностей, ${\displaystyle K}$ — длина входных последовательностей, ${\displaystyle W}$ — длина мотива, ${\displaystyle L}$ — алфавит, ${\displaystyle p_{lj}}$ — вероятность появления буквы ${\displaystyle l}$ в позиции ${\displaystyle j}$ мотива, ${\displaystyle p_{l0}}$ — вероятность появления буквы ${\displaystyle l}$ в любой позиции, ${\displaystyle f_{lj}}$ — наблюдаемая частота буквы ${\displaystyle l}$ в позиции ${\displaystyle j}$ мотива, ${\displaystyle f_{l0}}$ — наблюдаемая частота появления буквы ${\displaystyle l}$ в любой позиции.
3. Для каждой последовательности выбирается максимум функции правдоподобия из матрицы ${\displaystyle Z}$ и определяется позиция в последовательности, соответствующая этому максимуму. По соответствующим позициям строится выравнивание, вычисляются новые значения ПВМ по встречаемости букв в искомых колонках мотива^[3].
4. Пункты 2. и 3. повторяются, пока изменения значений ПВМ не станут меньше изначально заданного порога^[3].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоинства

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

Недостатки

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

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

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

Примечания

Эта страница в последний раз была отредактирована 13 мая 2022 в 01:45.