MaMF

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

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

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

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

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