MEME

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

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

## Содержание

* 1 История
* 2 Постановка задачи
* 3 Подготовительный этап
* 3.1 Подготовка последовательностей
* 3.2 Выбор входных параметров
* 4 Алгоритм
* 4.1 EM-алгоритм для поиска последовательностей
* 4.2 Вычисление наилучших входных параметров для алгоритма МЕМЕ
* 4.3 Алгоритм МЕМЕ
* 5 Время работы алгоритма
* 6 Достоинства
* 7 Недостатки
* 8 Реализация алгоритма
* 9 Примечания

## История

[править | править код]

Алгоритм 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-алгоритму подаётся:

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

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

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

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

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

1. Берется начальная ПВМ мотива. Она может быть задана или выбирается случайно.
2. По имеющимся значениям  p l c {\displaystyle p_{lc}} ПВМ для каждой позиции в каждой последовательности вычисляются значения матрицы  Z {\displaystyle Z} с помощью логарифма функции правдоподобия: log ⁡ ( l i k e l i h o o d ) = N ∑ j = 1 W ∑ l ∈ L f l j log ⁡ ( p l j ) + N ( K − W ) ∑ l ∈ L f l 0 log ⁡ ( p l 0 ) + N log ⁡ ( 1 K − W + 1 ) , {\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}}),} где  N {\displaystyle N} — количество входных последовательностей,  K {\displaystyle K} — длина входных последовательностей,  W {\displaystyle W} — длина мотива,  L {\displaystyle L} — алфавит,  p l j {\displaystyle p_{lj}} — вероятность появления буквы  l {\displaystyle l} в позиции  j {\displaystyle j} мотива,  p l 0 {\displaystyle p_{l0}} — вероятность появления буквы  l {\displaystyle l} в любой позиции,  f l j {\displaystyle f_{lj}} — наблюдаемая частота буквы  l {\displaystyle l} в позиции  j {\displaystyle j} мотива,  f l 0 {\displaystyle f_{l0}} — наблюдаемая частота появления буквы  l {\displaystyle l} в любой позиции.
3. Для каждой последовательности выбирается максимум функции правдоподобия из матрицы  Z {\displaystyle Z} и определяется позиция в последовательности, соответствующая этому максимуму. По соответствующим позициям строится выравнивание, вычисляются новые значения ПВМ по встречаемости букв в искомых колонках мотива[3].
4. Пункты 2. и 3. повторяются, пока изменения значений ПВМ не станут меньше изначально заданного порога[3].

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

[править | править код]

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

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

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

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

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

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

[править | править код]

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

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

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

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

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

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

[править | править код]

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

## Достоинства

[править | править код]

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

## Недостатки

[править | править код]

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

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

[править | править код]

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

## Примечания

[править | править код]

1. ↑ Patrik D'haeseleer. What are DNA sequence motifs? (англ.) // Nature Biotechnology. — 2006-04-01. — Vol. 24, iss. 4. — P. 423–425. — ISSN 1087-0156. — doi:10.1038/nbt0406-423. Архивировано 12 апреля 2017 года.
2. ↑ 1 2 T. L. Bailey, C. Elkan. Fitting a mixture model by expectation maximization to discover motifs in biopolymers // Proceedings. International Conference on Intelligent Systems for Molecular Biology. — 1994-01-01. — Т. 2. — С. 28–36. — ISSN 1553-0833. Архивировано 24 апреля 2017 года.
3. ↑ 1 2 3 4 5 6 7 8 Charles E. Lawrence, Andrew A. Reilly. An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences (англ.) // Proteins: Structure, Function, and Bioinformatics. — 1990-01-01. — Vol. 7, iss. 1. — P. 41–51. — ISSN 1097-0134. — doi:10.1002/prot.340070105. Архивировано 15 апреля 2017 года.
4. ↑ 1 2 3 4 Timothy L. Bailey, Nadya Williams, Chris Misleh, Wilfred W. Li. MEME: discovering and analyzing DNA and protein sequence motifs // Nucleic Acids Research. — 2006-07-01. — Т. 34, вып. suppl_2. — С. W369–W373. — ISSN 0305-1048. — doi:10.1093/nar/gkl198. Архивировано 15 апреля 2017 года.
5. ↑ Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant. MEME Suite: tools for motif discovery and searching // Nucleic Acids Research. — 2009-07-01. — Т. 37, вып. Web Server issue. — С. W202–W208. — ISSN 0305-1048. — doi:10.1093/nar/gkp335. Архивировано 11 декабря 2019 года.
6. ↑ 1 2 3 Introduction - MEME Suite (неопр.). meme-suite.org. Дата обращения: 14 апреля 2017. Архивировано 26 апреля 2017 года.
7. ↑ Expectation maximization algorithm for identifying protein-binding sites with variable lengths from unaligned DNA fragments - ScienceDirect (англ.). www.sciencedirect.com. Дата обращения: 15 апреля 2017.
8. ↑ 1 2 3 4 5 6 7 8 Timothy L. Bailey, Charles Elkan. Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization (англ.) // Machine Learning. — 1995-10-01. — Vol. 21, iss. 1-2. — P. 51–80. — doi:10.1023/A:1022617714621.
9. ↑ 1 2 3 The MEME Suite — Набор инструментов для поиска мотивов (неопр.). The MEME Suite. rothlab.ucdavis.edu. Дата обращения: 14 апреля 2017. Архивировано 8 февраля 2017 года.
10. ↑ A. P. Dempster, N. M. Laird, D. B. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm // Journal of the Royal Statistical Society. Series B (Methodological). — 1977-01-01. — Т. 39, вып. 1. — С. 1–38. Архивировано 19 июля 2017 года.
11. ↑ Avinash Achar, Pål Sætrom. RNA motif discovery: a computational overview // Biology Direct. — 2015-01-01. — Т. 10. — С. 61. — ISSN 1745-6150. — doi:10.1186/s13062-015-0090-5.

Эта статья входит в число добротных статей русскоязычного раздела Википедии.

|