MaMF

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

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

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

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

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