Interested Article - MEME
- 2020-06-20
- 1
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-алгоритму подаётся:
- набор последовательностей, принадлежащих алфавиту ;
- длина предполагаемого мотива .
Алгоритм возвращает возможную модель найденного мотива .
На каждом шаге алгоритма мотив определяется позиционно-весовой матрицей (ПВМ) размера , где — размер алфавита. В каждой ячейке ПВМ стоит вес , зависящий от вероятности появления буквы в колонке , где . Эти значения пересчитываются в ходе каждой итерации алгоритма .
Так как изначально неизвестно, где именно в последовательностях находится мотив, на каждом шаге алгоритма вычисляются значения матрицы , где элемент матрицы — правдоподобие того, что мотив начинается в последовательности с позиции .
Таким образом, алгоритм состоит из следующей последовательности шагов:
- Берется начальная ПВМ мотива. Она может быть задана или выбирается случайно.
-
По имеющимся значениям
ПВМ для каждой позиции в каждой последовательности вычисляются значения матрицы
с помощью логарифма
функции правдоподобия
:
- Для каждой последовательности выбирается максимум функции правдоподобия из матрицы и определяется позиция в последовательности, соответствующая этому максимуму. По соответствующим позициям строится выравнивание, вычисляются новые значения ПВМ по встречаемости букв в искомых колонках мотива .
- Пункты 2. и 3. повторяются, пока изменения значений ПВМ не станут меньше изначально заданного порога .
Вычисление наилучших входных параметров для алгоритма МЕМЕ
Для улучшения результата EM-алгоритма необходимо правильно выбрать набор стартовых параметров. Для этого есть несколько способов:
- Запустить алгоритм с различными возможными произвольными входными параметрами, а затем выбрать те, для которых значение функции правдоподобия будет наибольшим. Такой подход улучшает качество предсказания, но не гаратирует лучший результат .
- Использовать метод подпоследовательностей .
Метод подпоследовательностей основан на том, что искомый мотив должен соответствовать какой-то подпоследовательности длины в исходных данных. Для каждой такой подпоследовательности строятся ПВМ, с которых и стартует каждый запуск алгоритма EM. Наибольшее значение функции правдоподобия среди всех запусков алгоритма будет глобальным максимумом и даст искомый мотив. Именно этот принцип лимитирует поиск мотивов с гэпами .
По заданной подпоследовательности построить ПВМ можно различными способами. Алгоритм МЕМЕ использует следующий: частота буквы, соответствующей букве в подпоследовательности, принимается за , лучше всего алгоритм работает для . А вероятности для всех остальных букв принимаются за .
Оказывается, что в момент запуска алгоритма для подпоследовательности, соответствующей правильному мотиву, ЕМ-алгоритм сходится так быстро, что достаточно одной итерации. Поэтому для экономии времени достаточно каждый раз запускать только одну итерацию ЕМ-алгоритма, что и реализовано в алгоритме МЕМЕ .
Алгоритм МЕМЕ
Алгоритм МЕМЕ основан на многократном применении ЕМ-алгоритма для поиска мотива в последовательностях. На вход алгоритму МЕМЕ подаётся:
- набор последовательностей, принадлежащих алфавиту ;
- длина предполагаемого мотива ;
- ожидаемое количество копий мотива;
- количество различных мотивов .
Алгоритм ЕМ модифицируется до следующего:
- Выбираются начальные параметры методом подпоследовательностей.
- Для каждого набора входных параметров осуществляется одна итерация ЕМ-алгоритма. Выбирается наибольшее значение функции правдоподобия из всех запусков.
- Полученный мотив сохраняется и удаляется из входных последовательностей для поиска следующих.
- Пункты 1., 2. и 3. повторяются для поиска заданного количества мотивов .
Обнаруженные мотивы на выходе программы подаются в виде LOGO .
Время работы алгоритма
Алгоритм МЕМЕ поиска мотива длины совершает шагов, где — неизвестная константа (между 10 и 100), — это общее количество букв заданного алфавита во входных последовательностях . То есть сложность алгоритма оказывается .
Достоинства
В отличие от EM, MEME позволяет работать и эффективно находить мотивы в последовательностях, содержащих более одной копии мотива или не содержащих мотив. Последние при этом расцениваются алгоритмом, как шум . Большим плюсом также является возможность поиска нескольких различных мотивов в одном наборе входных последовательностей и поиск глобального оптимального мотива, тогда как EM часто останавливается на локально оптимальном, который может при этом не являться мотивом вообще . Существует реализация алгоритма в виде программы для ПК и веб сервера с удобным интерфейсом с набором дополнительных программ для дальнейшей работы с найденным мотивом .
Недостатки
Алгоритмом MEME плохо распознаются мотивы в длинных последовательностях, кроме того большая длина последовательностей сильно увеличивают время работы алгоритма . Также в алгоритме MEME делается важное базовое предположение о равновероятности появления мотива в любой части последовательности. Такой подход не подходит о для поиска мотива в последовательностях РНК , так как они образуют вторичные и третичные структуры, что делает появление мотива более или менее вероятным в зависимости от структуры . Алгоритм не позволяет найти мотивы с гэпами, так как сама алгоритма не предполагает их поиск.
Реализация алгоритма
На основе данного алгоритма реализован инструмент MEME Suite, доступный в веб-версии и для ПК , по состоянию на 2017 год он поддерживается и обновляется.
Примечания
- Patrik D'haeseleer. (англ.) // Nature Biotechnology. — 2006-04-01. — Vol. 24 , iss. 4 . — P. 423–425 . — ISSN . — doi : . 12 апреля 2017 года.
- ↑ T. L. Bailey, C. Elkan. // Proceedings. International Conference on Intelligent Systems for Molecular Biology. — 1994-01-01. — Т. 2 . — С. 28–36 . — ISSN . 24 апреля 2017 года.
- ↑ Charles E. Lawrence, Andrew A. Reilly. (англ.) // Proteins: Structure, Function, and Bioinformatics. — 1990-01-01. — Vol. 7 , iss. 1 . — P. 41–51 . — ISSN . — doi : . 15 апреля 2017 года.
- ↑ Timothy L. Bailey, Nadya Williams, Chris Misleh, Wilfred W. Li. // Nucleic Acids Research. — 2006-07-01. — Т. 34 , вып. suppl_2 . — С. W369–W373 . — ISSN . — doi : . 15 апреля 2017 года.
- Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant. // Nucleic Acids Research. — 2009-07-01. — Т. 37 , вып. Web Server issue . — С. W202–W208 . — ISSN . — doi : . 11 декабря 2019 года.
- ↑ . meme-suite.org. Дата обращения: 14 апреля 2017. 26 апреля 2017 года.
- (англ.) . 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 : .
- ↑ . The MEME Suite . rothlab.ucdavis.edu. Дата обращения: 14 апреля 2017. 8 февраля 2017 года.
- A. P. Dempster, N. M. Laird, D. B. Rubin. // Journal of the Royal Statistical Society. Series B (Methodological). — 1977-01-01. — Т. 39 , вып. 1 . — С. 1–38 . 19 июля 2017 года.
- Avinash Achar, Pål Sætrom. // Biology Direct. — 2015-01-01. — Т. 10 . — С. 61 . — ISSN . — doi : .
- 2020-06-20
- 1