MaMF - MaMF

MaMF, или Mammalian Motif Finder, представляет собой алгоритм для идентификации мотивы которому факторы транскрипции связывать.

Алгоритм принимает на вход набор промоутер последовательностей и ширины мотива (w), а на выходе получается ранжированный список из 30 предсказанных мотивов (каждый мотив определяется набором из N последовательностей, где N - параметр).

Алгоритм во-первых индексы каждая подпоследовательность длины n, где n - параметр около 4-6 пар оснований, в каждом промоутере, чтобы их можно было эффективно найти. Затем этот индекс используется для построения списка всех пар последовательностей длины w, так что каждая последовательность имеет общий н-мер, и каждая последовательность образует незаполненный выравнивание с подстрокой длины w из строки длиной 2w вокруг совпадения с оценкой, превышающей отсечку.

Затем оцениваются пары последовательностей. Функция подсчета очков отдает предпочтение парам, которые очень похожи, но не отдает предпочтение последовательностям, которые очень часто встречаются в целевом геноме. 1000 пар, набравших наибольшее количество очков, сохраняются, а остальные отбрасываются. Каждый из этих 1000 «исходных» мотивов затем используется для итеративного поиска дополнительных последовательностей длины, которые максимизируют оценку ( жадный алгоритм ), пока не будут достигнуты N последовательностей для этого мотива.

Очень похожие мотивы отбрасываются, и 30 мотивов с наивысшими оценками возвращаются в качестве вывода.

Рекомендации

• Лоуренс С. Хон и Аджай Н. Джайн: «Детерминированный алгоритм поиска мотивов с приложением к геному человека». Биоинформатика 2006 22 (9): 1047-1054