View source for MaMF

{{Short description|Algorithm}}
{{Notability|date=August 2021}}
'''MaMF''', or Mammalian Motif Finder, is an algorithm for identifying [[Sequence motif|motifs]] to which [[transcription factors]] bind.<ref>{{cite journal |last1=Hon |first1=Lawrence S |last2=Jain |first2=Ajay N |title=A deterministic motif finding algorithm with application to the human genome |journal=Bioinformatics |date=1 May 2006 |volume=22 |issue=9 |pages=1047–1054 |doi=10.1093/bioinformatics/btl037|pmid=16455748 |doi-access=free }}</ref>
The algorithm takes as input a set of [[promoter (biology)|promoter]] sequences, and a motif width(w), and as output, produces a ranked list of 30 predicted motifs(each motif is defined by a set of N sequences, where N is a parameter).
The algorithm firstly [[index (database)|index]]es each sub-sequence of length n, where n is a parameter around 4-6 [[base pairs]], in each promoter, so they can be looked up efficiently. This index is then used to build a list of all pairs of sequences of length w, such that each sequence shares an [[n-mer]], and each sequence forms an ungapped [[Sequence alignment|alignment]] with a substring of length w from the string of length 2w around the match, with a score exceeding a cut-off.
The pairs of sequences are then scored. The scoring function favours pairs which are very similar, but disfavours sequences which are very common in the target genome. The 1000 highest scoring pairs are kept, and the others are discarded. Each of these 1000 'seed' motifs are then used to search iteratively search for further sequences of length which maximise the score(a [[greedy algorithm]]), until N sequences for that motif are reached.
Very similar motifs are discarded, and the 30 highest scoring motifs are returned as output.
== References ==
{{reflist}}
[[Category:Search algorithms]]
[[Category:Bioinformatics]]