MaMF - MaMF

MaMF, nebo Mammalian Motif Finder, je algoritmus pro identifikaci motivy ke kterému transkripční faktory svázat.

Algoritmus bere jako vstup sadu promotér sekvence a šířka motivu (w) a jako výstup vytvoří seřazený seznam 30 predikovaných motivů (každý motiv je definován sadou N sekvencí, kde N je parametr).

Nejprve algoritmus indexy každá subsekvence délky n, kde n je parametr kolem 4-6 základní páry, v každém pořadateli, aby je bylo možné efektivně vyhledat. Tento index se poté použije k vytvoření seznamu všech párů sekvencí délky w, takže každá sekvence sdílí n-mer a každá sekvence tvoří nevyužitý zarovnání s podřetězcem délky w z řetězce o délce 2w kolem zápasu, se skóre přesahujícím cut-off.

Dvojice sekvencí se poté skórují. Funkce skórování upřednostňuje páry, které jsou si velmi podobné, ale znevýhodňuje sekvence, které jsou v cílovém genomu velmi běžné. 1000 nejlépe skórujících párů je uchováno a ostatní jsou zahozeny. Každý z těchto 1000 motivů „seed“ se poté použije k iterativnímu vyhledávání dalších sekvencí délky, které maximalizují skóre (a chamtivý algoritmus ), dokud není dosaženo N sekvencí pro daný motiv.

Velmi podobné motivy jsou zahozeny a 30 nejlépe hodnocených motivů je vráceno jako výstup.

Reference

• Lawrence S Hon a Ajay N Jain: „Algoritmus deterministického hledání motivu s aplikací na lidský genom“. Bioinformatics 2006 22 (9): 1047-1054