MEME: различия между версиями

[непроверенная версия]

Содержимое удалено Содержимое добавлено

Линейный

Версия от 11:01, 17 апреля 2017

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 работали Тимоти Бейли и Уильям Стэффорд Нобель, вклад в проект анесли также Чарльз Элкан и Майкл Грибсков. В настоящий момент MEME Suite поддерживается грантом NIH, а вебсервер также получает помощь от Google и Amazon^[6].

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

Берется начальная ПВМ мотива. Она может быть задана или выбирается случайно.
По имеющимся значениям $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$ в любой позиции.
Для каждой последовательности выбирается максимум функции правдоподобия из матрицы $Z$ и определяется позиция в последовательности, соответствующая этому максимуму. По соответствующим позициям строится выравнивание, вычисляются новые значения ПВМ по встречаемости букв в искомых колонках мотива^[3].
Пункты 2. и 3. повторяются, пока изменения значений ПВМ не станут меньше изначально заданного порога^[3].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоинства

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

Недостатки

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

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

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

Ссылки

↑ 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.
↑ 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.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ 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.
↑ ¹ ² ³ 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.
↑ 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.
↑ ¹ ² Introduction - MEME Suite (неопр.). meme-suite.org. Дата обращения: 14 апреля 2017.
↑ Expectation maximization algorithm for identifying protein-binding sites with variable lengths from unaligned DNA fragments - ScienceDirect (англ.). www.sciencedirect.com. Дата обращения: 15 апреля 2017.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ 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.
↑ ¹ ² ³ The MEME Suite — Набор инструментов для поиска мотивов (неопр.). The MEME Suite. rothlab.ucdavis.edu. Дата обращения: 14 апреля 2017.
↑ 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.
↑ 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.

[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.

[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.

[:2-3] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ 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.

[:0-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.

[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.

[:1-6] ¹ ² Introduction - MEME Suite (неопр.). meme-suite.org. Дата обращения: 14 апреля 2017.

[7] Expectation maximization algorithm for identifying protein-binding sites with variable lengths from unaligned DNA fragments - ScienceDirect (англ.). www.sciencedirect.com. Дата обращения: 15 апреля 2017.

[:3-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.

[:4-9] ¹ ² ³ The MEME Suite — Набор инструментов для поиска мотивов (неопр.). The MEME Suite. rothlab.ucdavis.edu. Дата обращения: 14 апреля 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.

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Строка 62: / Строка 62: @@
 == Достоинства ==
+В отличие от EM, MEME позволяет работать и эффективно находить мотивы в последовательностях, содержащих более одной копии мотива или не содержащих мотив. Последние при этом расцениваются алгоритмом, как шум<ref name=":3" />. Большим плюсом также является возможность поиска нескольких различных мотивов в одном наборе входных последовательностей<ref name=":3" /> и поиск глобального оптимального мотива, тогда как EM часто останавливается на локально оптимальном, который может при этом не являться мотивом вообще<ref>{{Статья|автор=A. P. Dempster, N. M. Laird, D. B. Rubin|заглавие=Maximum Likelihood from Incomplete Data via the EM Algorithm|ссылка=http://www.jstor.org/stable/2984875|издание=Journal of the Royal Statistical Society. Series B (Methodological)|год=1977-01-01|том=39|выпуск=1|страницы=1–38}}</ref>. Существует реализация алгоритма в виде программы для ПК и веб сервера с удобным интерфейсом с набором дополнительных программ для дальнейшей работы с найденным мотивом<ref name=":4" />.
-* Возможность наличия более одной копии мотива на последовательность или отсутствие мотива<ref name=":3" />.
-* Возможность поиска нескольких различных мотивов в одном наборе входных последовательностей<ref name=":3" />.
-* Поиск глобального оптимального мотива<ref>{{Статья|автор=A. P. Dempster, N. M. Laird, D. B. Rubin|заглавие=Maximum Likelihood from Incomplete Data via the EM Algorithm|ссылка=http://www.jstor.org/stable/2984875|издание=Journal of the Royal Statistical Society. Series B (Methodological)|год=1977-01-01|том=39|выпуск=1|страницы=1–38}}</ref>.
-* Существование веб сервера и программы для ПК с реализацией алгоритма<ref name=":4" />.
 == Недостатки ==
+MEME плохо распознаются мотивы в длинных последовательностях, а также сильно увеличивают время работы алгоритма<ref name=":0" /><ref name=":4" />. Также в алгоритме MEME делается важное базовое предположение о равновероятности появления мотива в любой части последовательности. Такой подход не подходит о для поиска мотива в последовательностях [[Рибонуклеиновая кислота|РНК]], так как они образовывают вторичные и третичные структуры, что делает появление мотива более или менее вероятным в зависимости от структуры<ref>{{Статья|автор=Avinash Achar, Pål Sætrom|заглавие=RNA motif discovery: a computational overview|ссылка=http://dx.doi.org/10.1186/s13062-015-0090-5|издание=Biology Direct|год=2015-01-01|том=10|страницы=61|issn=1745-6150|doi=10.1186/s13062-015-0090-5}}</ref>. Алгоритм не позволяет найти мотивы с гэпами, т.к. сама [[MEME#Постановка задачи|постановка задачи]] алгоритма не предполагает их поиск.
-* Плохое распознавание мотивов в длинных последовательностях.
-* Не подходит для поиска мотивов в РНК, так как учитывает только последовательность, но не и вторичную и третичную структуру.
-* Не позволяет найти мотивы с гэпами.
 ==  Реализация алгоритма ==