MEME

Multiple EM for Motif Elicitation ( MEME ) je stejnojmenný algoritmus a nástroj, který je implementací algoritmu pro hledání motivů v biologických sekvencích proteinů a DNA . Algoritmus je založen na opakované aplikaci metody maximální věrohodnosti . Motiv je krátká sekvence nukleotidů nebo aminokyselin , která je společná pro nějakou sadu sekvencí.

Hledání motivů je důležitým úkolem v biologii, protože přítomnost motivu v sekvenci může sloužit jako signál pro rozpoznání sekvence pro transkripční faktory nebo restrikční endonukleázy [1] .

Historie

Algoritmus MEME vyvinuli v roce 1994 Timothy Bailey a Charles Elkan [2] . Jde o rozšíření metody maximální věrohodnosti pro hledání motivů , kterou v roce 1990 publikovali Lawrence a Reilly [3] . Původní metoda umožňovala najít pouze jeden motiv v sadě sekvencí a tento motiv byl lokálně optimální, protože algoritmus silně závisí na volbě výchozích parametrů. Správnost jeho činnosti také silně závisela na hladině hluku v uvažovaných sekvencích. Metoda MEME umožnila tyto nedostatky obejít. V roce 1996 byl vytvořen webový server obsahující implementaci MEME, který v letech 2000 až 2006 využívalo asi 800 unikátních návštěvníků [4] . A v roce 2009 byl představen balík MEME Suite obsahující nejen implementaci MEME, ale i mnoho dalších souvisejících programů [5] . Celkem na tvorbě MEME Suite pracovali tito lidé: na projektu se podíleli i Timothy Bailey, William Stafford Nobel, Charles Elkan a Michael Gribskov. Od roku 2017 je MEME Suite podporován grantem NIH a webový server také dostává pomoc od společností Google a Amazon [6] .

Prohlášení o problému

Je nutné identifikovat jeden nebo více společných motivů v sadě chybně zarovnaných nukleotidových nebo aminokyselinových sekvencí, z nichž každá obsahuje jeden, více nebo žádný motiv. V tomto případě uvažujeme motivy bez mezer (mezer), které mají společnou biologickou funkci. Mohou to být například cíle jednoho proteinu vázajícího DNA. MEME využívá reprezentaci biologického motivu ve formě matice pozice-váha (PWM) [2] .

Přípravná fáze

Příprava sekvencí

V žádné sadě sekvencí není možné detekovat společný motiv, proto, aby algoritmus správně fungoval, musí být sekvence pečlivě vybrány a připraveny: v této sadě je třeba očekávat společný motiv (například je známo, že sekvence se vážou k jedinému transkripčnímu faktoru ) a sekvence musí být tak krátké, aby pokud možno (ideálně < 1000 nukleotidů ) [4] .

Volba vstupních parametrů

Výstup MEME standardně neobsahuje více než tři motivy o délce od 6 do 50, které se nacházejí v dopředném i zpětném řetězci vstupních sekvencí [6] . Pokud je znám biologický význam hledaných objektů, pak lze odhadnout a nastavit počet a délku motivů, které se v této sadě sekvencí očekávají. Tím se zlepší kvalita predikce v případě, že motiv nevyhovuje výchozím parametrům [4] .

Algoritmus

EM-algoritmus pro hledání sekvencí

Vstup do EM algoritmu je:

soubor sekvencí patřících do abecedy ; $L$
délka údajného motivu [3] . $W$

Algoritmus vrací možný model nalezeného motivu [3] .

V každém kroku algoritmu je motiv určen maticí pozic a váhy (PWM) o velikosti , kde je velikost abecedy. Každá buňka PVM má váhu , která závisí na pravděpodobnosti, že se písmeno objeví ve sloupci , kde . Tyto hodnoty se přepočítávají během každé iterace algoritmu [3] . $|L|\times W$ $|L|$ ${\displaystyle p_{lc))$ $l$ $C$ $1\leq c\leq W$

Vzhledem k tomu, že zpočátku není známo, kde přesně v sekvencích se motiv nachází, jsou v každém kroku algoritmu vypočteny hodnoty matice , kde prvkem matice je pravděpodobnost, že motiv začíná v sekvenci od pozice [3 ] . $Z$ $z_{{ij}}$ $i$ $j$

Algoritmus se tedy skládá z následující sekvence kroků:

Vezme se počáteční PVM motivu. Může být dán nebo vybrán náhodně.
Na základě dostupných hodnot SMP pro každou pozici v každé sekvenci se hodnoty matice vypočítají pomocí logaritmu věrohodnostní funkce : ${\displaystyle p_{lc))$ $Z$ log ⁡ ( l i k E l i h Ó Ó d ) = N ∑ j = jeden W ∑ l ∈ L F l j log ⁡ ( p l j ) + N ( K − W ) ∑ l ∈ L F l 0 log ⁡ ( p l 0 ) + N log ⁡ ( jeden K − W + jeden ) , {\displaystyle \log(pravděpodobnost)=N\součet _{j=1}^{W}\součet _{l\in L}f_{lj}\log(p_{lj})+N(KW)\součet _{l\in L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),} $\log(pravděpodobnost)=N\součet _{j=1}^{W}\součet _{l\in L}f_{lj}\log(p_{lj})+N(KW)\součet _{l\in L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),$ kde je počet vstupních sekvencí, je délka vstupních sekvencí, je délka motivu, je abeceda, je pravděpodobnost výskytu písmene na pozici motivu, je pravděpodobnost výskytu písmene na libovolné pozici, je pozorovaná frekvence písmene v pozici motivu, je pozorovaná frekvence písmena v libovolné poloze . $N$ $K$ $W$ $L$ ${\displaystyle p_{lj))$ $l$ $j$ ${\displaystyle p_{l0))$ $l$ ${\displaystyle f_{lj))$ $l$ $j$ ${\displaystyle f_{l0))$ $l$
Pro každou sekvenci se z matice vybere maximum věrohodnostní funkce a určí se pozice v sekvenci odpovídající tomuto maximu. Zarovnání je sestaveno podle odpovídajících pozic, nové hodnoty PWM jsou počítány podle výskytu písmen v požadovaných sloupcích motivu [3] . $Z$
Body 2. a 3. se opakují, dokud změny hodnot PVM neklesnou pod původně nastavený práh [3] .

Výpočet nejlepších vstupních parametrů pro algoritmus MEME

Pro zlepšení výsledku EM algoritmu je nutné zvolit správnou sadu startovacích parametrů. Existuje několik způsobů, jak to provést:

Spusťte algoritmus s různými možnými libovolnými vstupy a poté vyberte ty, pro které bude pravděpodobnostní funkce největší. Tento přístup zlepšuje kvalitu predikce, ale nezaručuje lepší výsledek [3] [7] .
Použijte metodu subsekvence [8] .

Metoda subsekvence je založena na tom, že požadovaný motiv musí odpovídat nějaké subsekvenci délky v původních datech. Pro každou takovou subsekvenci jsou konstruovány PVM, od kterých začíná každé spuštění EM algoritmu. Největší hodnota věrohodnostní funkce ze všech běhů algoritmu bude globálním maximem a poskytne požadovaný motiv. Právě tento princip omezuje hledání motivů s mezerami [8] . $W$

Podle dané podsekvence lze PSM konstruovat různými způsoby. Algoritmus MEME používá následující: četnost písmene odpovídající písmenu v podsekvenci je brána jako , algoritmus funguje nejlépe pro . A pravděpodobnosti pro všechna ostatní písmena jsou brány jako [8] . $0<X<1$ $0{,}4\leq X\leq 0{,}8$ ${\frac {1-X}{|L|-1}}$

Ukazuje se, že v okamžiku spuštění algoritmu pro podsekvenci odpovídající správnému motivu konverguje EM algoritmus tak rychle, že stačí jedna iterace. Pro úsporu času tedy stačí spustit vždy pouze jednu iteraci EM algoritmu, která je implementována v MEME algoritmu [8] .

MEME algoritmus

Algoritmus MEME je založen na opakované aplikaci EM algoritmu pro hledání motivu v sekvencích. Vstup do MEME algoritmu je:

soubor sekvencí patřících do abecedy ; $L$
délka údajného motivu ; $W$
předpokládaný počet kopií motivu;
množství různých motivů [8] .

Algoritmus EM je upraven na následující:

Počáteční parametry se volí metodou subsekvence.
Pro každou sadu vstupních parametrů se provede jedna iterace EM algoritmu. Ze všech běhů se vybere největší hodnota věrohodnostní funkce.
Výsledný motiv se uloží a odebere ze vstupních sekvencí pro hledání dalších.
Položky 1., 2. a 3. se pro vyhledání daného počtu motivů opakují [8] .

Objevené motivy na výstupu programu jsou uvedeny ve formě LOGO .

Doba běhu algoritmu

Algoritmus hledání motivu délky MEME provádí kroky, kde neznámá konstanta (mezi 10 a 100) je celkový počet písmen dané abecedy ve vstupních sekvencích [9] . To znamená, že složitost algoritmu se ukazuje jako . $W$ ${\displaystyle k*W*n^{2))$ $k$ $n$ $O(W*n^{2})$

Výhody

Na rozdíl od EM vám MEME umožňuje pracovat a efektivně vyhledávat motivy v sekvencích obsahujících více než jednu kopii motivu nebo neobsahující motiv. Ty jsou algoritmem považovány za šum [8] . Velkým plusem je také možnost vyhledávat více různých motivů v jedné sadě vstupních sekvencí [8] a hledat globální optimální motiv, přičemž EM se často zastaví u lokálně optimálního, který motivem vůbec být nemusí [10 ] . Existuje implementace algoritmu ve formě programu pro PC a webový server s pohodlným rozhraním se sadou doplňkových programů pro další práci s nalezeným motivem [9] .

Nevýhody

Algoritmus MEME špatně rozpoznává motivy v dlouhých sekvencích, navíc velká délka sekvencí značně prodlužuje dobu běhu algoritmu [4] [9] . Algoritmus MEME také vytváří důležitý základní předpoklad o ekvipravděpodobnosti výskytu motivu v jakékoli části sekvence. Tento přístup není vhodný pro hledání motivu v sekvencích RNA , protože tvoří sekundární a terciární struktury, což činí výskyt motivu více či méně pravděpodobným v závislosti na struktuře [11] . Algoritmus neumožňuje najít motivy s mezerami, protože samotná formulace problému algoritmu neznamená jejich hledání.

Implementace algoritmu

Na základě tohoto algoritmu je implementován nástroj MEME Suite dostupný ve webové verzi i pro PC [6] , od roku 2017 je podporován a aktualizován.

Poznámky

↑ Patrik D'haeseleer. Co jsou motivy sekvence DNA? (anglicky) // Nature Biotechnology. - 2006-04-01. — Sv. 24 , iss. 4 . — S. 423–425 . — ISSN 1087-0156 . - doi : 10.1038/nbt0406-423 . Archivováno z originálu 12. dubna 2017.
↑ 1 2 T. L. Bailey, C. Elkan. Přizpůsobení modelu směsi maximalizací očekávání k objevení motivů v biopolymerech // Proceedings. Mezinárodní konference o inteligentních systémech pro molekulární biologii. — 1994-01-01. - T. 2 . — S. 28–36 . — ISSN 1553-0833 . Archivováno z originálu 24. dubna 2017.
↑ 1 2 3 4 5 6 7 8 Charles E. Lawrence, Andrew A. Reilly. Algoritmus maximalizace očekávání (EM) pro identifikaci a charakterizaci společných míst v nezarovnaných biopolymerních sekvencích // Proteiny: struktura, funkce a bioinformatika. — 1990-01-01. — Sv. 7 , iss. 1 . — S. 41–51 . — ISSN 1097-0134 . - doi : 10.1002/prot.340070105 . Archivováno z originálu 15. dubna 2017.
↑ 1 2 3 4 Timothy L. Bailey, Nadya Williams, Chris Misleh, Wilfred W. Li. MEME: objevování a analýza motivů DNA a proteinových sekvencí // Nucleic Acids Research. - 2006-07-01. - T. 34 , č.p. suppl_2 . — S. W369–W373 . — ISSN 0305-1048 . doi : 10.1093 / nar/gkl198 . Archivováno z originálu 15. dubna 2017.
↑ Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant. MEME Suite: nástroje pro objevování a vyhledávání motivů // Nucleic Acids Research. — 2009-07-01. - T. 37 , č.p. Problém s webovým serverem . — C. W202–W208 . — ISSN 0305-1048 . - doi : 10.1093/nar/gkp335 . Archivováno z originálu 11. prosince 2019.
↑ 1 2 3 Úvod - MEME Suite . meme-suite.org. Získáno 14. dubna 2017. Archivováno z originálu 26. dubna 2017. (neurčitý)
↑ Algoritmus maximalizace očekávání pro identifikaci vazebných míst pro proteiny s proměnlivou délkou z nezarovnaných fragmentů DNA - ScienceDirect . www.sciencedirect.com. Datum přístupu: 15. dubna 2017.
↑ 1 2 3 4 5 6 7 8 Timothy L. Bailey, Charles Elkan. Učení více motivů v biopolymerech bez dozoru pomocí maximalizace očekávání // Strojové učení. — 10.10.1995. — Sv. 21 , iss. 1-2 . — S. 51–80 . - doi : 10.1023/A:1022617714621 .
↑ 1 2 3 MEME Suite – sada nástrojů pro hledání motivů . MEME Suite . rothlab.ucdavis.edu. Získáno 14. 4. 2017. Archivováno z originálu 8. 2. 2017. (neurčitý)
↑ A. P. Dempster, N. M. Laird, D. B. Rubin. Maximální pravděpodobnost z neúplných dat prostřednictvím EM Algorithm // Journal of the Royal Statistical Society. Řada B (Metodická). — 1. 1. 1977. - T. 39 , č.p. 1 . — S. 1–38 . Archivováno z originálu 19. července 2017.
↑ Avinash Achar, Pål Sætrom. Objev RNA motivu: výpočetní přehled // Biology Direct. — 2015-01-01. - T. 10 . - S. 61 . — ISSN 1745-6150 . - doi : 10.1186/s13062-015-0090-5 .