EU EU

Multiple EM for Motif Elicitation ( MEME ) este un algoritm și un instrument cu același nume, care este o implementare a algoritmului, pentru căutarea motivelor în secvențele biologice de proteine și ADN . Algoritmul se bazează pe aplicarea repetată a metodei probabilității maxime . Un motiv este o secvență scurtă de nucleotide sau aminoacizi care este comună unui set de secvențe.

Căutarea motivelor este o sarcină importantă în biologie, deoarece prezența unui motiv într-o secvență poate servi ca semnal pentru recunoașterea secvenței pentru factorii de transcripție sau endonucleazele de restricție [1] .

Istorie

Algoritmul MEME a fost dezvoltat în 1994 de Timothy Bailey și Charles Elkan [2] . Este o extensie a metodei de maximă probabilitate pentru găsirea motivelor , care a fost publicată în 1990 de Lawrence și Reilly [3] . Metoda originală a făcut posibilă găsirea unui singur motiv într-un set de secvențe, iar acest motiv a fost optim local, deoarece algoritmul depinde puternic de alegerea parametrilor de pornire. Corectitudinea funcționării sale a depins puternic și de nivelul de zgomot din secvențele considerate. Metoda MEME a făcut posibilă ocolirea acestor neajunsuri. În 1996, a fost creat un server web care conținea o implementare a MEME, care a fost folosit de aproximativ 800 de vizitatori unici între 2000 și 2006 [4] . Și în 2009 a fost prezentat pachetul MEME Suite, care conține nu doar implementarea MEME, ci și multe alte programe conexe [5] . În total, următoarele persoane au lucrat la crearea Suitei MEME: Timothy Bailey, William Stafford Nobel, Charles Elkan și Michael Gribskov au contribuit și ei la proiect. Din 2017, suita MEME este susținută de un grant NIH , iar serverul web primește și ajutor de la Google și Amazon [6] .

Enunțul problemei

Este necesar să se identifice unul sau mai multe motive comune într-un set de secvențe de nucleotide sau aminoacizi nealiniate, fiecare conținând unul, mai multe motive sau niciun motiv. În acest caz, luăm în considerare motivele fără lacune (lacune) care au o funcție biologică comună. De exemplu, ele pot fi ținte ale unei singure proteine de legare a ADN-ului. MEME folosește reprezentarea unui motiv biologic sub forma unei matrice poziție-greutate (PWM) [2] .

Etapa pregătitoare

Pregătirea secvențelor

Nu este posibil să se detecteze un motiv comun în niciun set de secvențe, prin urmare, pentru ca algoritmul să funcționeze corect, secvențele trebuie selectate și pregătite cu atenție: trebuie așteptat un motiv comun în acest set (de exemplu, se știe că secvențele se leagă la un singur factor de transcripție ), iar secvențele trebuie să fie atât de scurte încât pe cât posibil (ideal <1000 de nucleotide ) [4] .

Alegerea parametrilor de intrare

În mod implicit, ieșirea MEME conține nu mai mult de trei motive de lungime de la 6 la 50, găsite atât pe lanțul direct cât și pe cel invers al secvențelor de intrare [6] . Dacă semnificația biologică a obiectelor de căutare este cunoscută, atunci se poate ghici și seta numărul și lungimea motivelor care sunt așteptate în acest set de secvențe. Acest lucru va îmbunătăți calitatea predicției în cazul în care motivul nu se potrivește parametrilor impliciti [4] .

Algoritm

EM-algoritm pentru găsirea secvențelor

Intrarea în algoritmul EM este:

un set de secvențe aparținând alfabetului ; $L$
lungimea presupusului motiv [3] . $W$

Algoritmul returnează un posibil model al motivului găsit [3] .

La fiecare pas al algoritmului, motivul este determinat de o matrice poziție-greutate (PWM) de dimensiune , unde este dimensiunea alfabetului. Fiecare celulă a PVM are o pondere care depinde de probabilitatea ca o literă să apară în coloană , unde . Aceste valori sunt recalculate în timpul fiecărei iterații a algoritmului [3] . $|L|\times W$ $|L|$ $p_{lc)$ $l$ $c$ $1\leq c\leq W$

Deoarece inițial nu se știe unde exact în secvențe se află motivul, la fiecare pas al algoritmului se calculează valorile matricei , unde elementul matricei este probabilitatea ca motivul să înceapă în secvența din poziția [3]. ] . $Z$ $z_{{ij}}$ $i$ $j$

Astfel, algoritmul constă din următoarea secvență de pași:

Se ia PVM inițial al motivului. Poate fi dat sau ales aleatoriu.
Pe baza valorilor SMP disponibile pentru fiecare poziție din fiecare secvență, valorile matricei sunt calculate folosind logaritmul funcției de probabilitate : $p_{lc)$ $Z$ Buturuga ⁡ ( l i k e l i h o o d ) = N ∑ j = unu W ∑ l ∈ L f l j Buturuga ⁡ ( p l j ) + N ( K − W ) ∑ l ∈ L f l 0 Buturuga ⁡ ( p l 0 ) + N Buturuga ⁡ ( unu K − W + unu ) , {\displaystyle \log(probabilitate)=N\sum _{j=1}^{W}\sum _{l\in L}f_{lj}\log(p_{lj})+N(KW)\sum _{l\în L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),} $\log(probabilitate)=N\sum _{j=1}^{W}\sum _{l\in L}f_{lj}\log(p_{lj})+N(KW)\sum _{l\în L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),$ unde este numărul de secvențe de intrare, este lungimea secvențelor de intrare, este lungimea motivului, este alfabetul, este probabilitatea ca o literă să apară în poziția motivului, este probabilitatea ca literă să apară în orice poziție, este frecvența observată a literei în poziția motivului, este frecvența observată a literei în orice poziție. $N$ $K$ $W$ $L$ $p_{lj)$ $l$ $j$ $p_{l0)$ $l$ $f_{lj)$ $l$ $j$ $f_{l0)$ $l$
Pentru fiecare secvență, maximul funcției de probabilitate este selectat din matrice și este determinată poziția în secvența corespunzătoare acestui maxim. Alinierea este construită în funcție de pozițiile corespunzătoare, noile valori ale PWM sunt calculate în funcție de apariția literelor în coloanele dorite ale motivului [3] . $Z$
Punctele 2. și 3. se repetă până când modificările valorilor PVM devin mai mici decât pragul stabilit inițial [3] .

Calculul celor mai buni parametri de intrare pentru algoritmul MEME

Pentru a îmbunătăți rezultatul algoritmului EM, este necesar să alegeți setul potrivit de parametri de pornire. Există mai multe moduri de a face acest lucru:

Rulați algoritmul cu diferite intrări arbitrare posibile și apoi alegeți-le pe acelea pentru care funcția de probabilitate va fi cea mai mare. Această abordare îmbunătățește calitatea predicției, dar nu garantează un rezultat mai bun [3] [7] .
Folosiți metoda subsecvenței [8] .

Metoda subsecvenței se bazează pe faptul că motivul dorit trebuie să corespundă unei anumite subsecvențe de lungime în datele originale. Pentru fiecare astfel de secvență, sunt construite PVM-uri, de la care începe fiecare lansare a algoritmului EM. Cea mai mare valoare a funcției de probabilitate dintre toate rulările algoritmului va fi maximul global și va oferi motivul dorit. Acest principiu limitează căutarea motivelor cu lacune [8] . $W$

Conform unei subsecvențe date, un PSM poate fi construit în diferite moduri. Algoritmul MEME folosește următoarele: frecvența literei corespunzătoare literei din subsecvența este luată ca , algoritmul funcționează cel mai bine pentru . Și probabilitățile pentru toate celelalte litere sunt luate ca [8] . $0<X<1$ $0{,}4\leq X\leq 0{,}8$ ${\frac {1-X}{|L|-1}}$

Se pare că în momentul rulării algoritmului pentru o subsecvență corespunzătoare motivului corect, algoritmul EM converge atât de repede încât o iterație este suficientă. Prin urmare, pentru a economisi timp, este suficient să rulați o singură iterație a algoritmului EM de fiecare dată, care este implementată în algoritmul MEME [8] .

Algoritmul MEME

Algoritmul MEME se bazează pe aplicarea repetată a algoritmului EM pentru a căuta un motiv în secvențe. Intrarea în algoritmul MEME este:

un set de secvențe aparținând alfabetului ; $L$
lungimea presupusului motiv ; $W$
numărul așteptat de copii ale motivului;
numărul de motive diferite [8] .

Algoritmul EM este modificat astfel:

Parametrii inițiali sunt aleși prin metoda subsecvenței.
Pentru fiecare set de parametri de intrare, se efectuează o iterație a algoritmului EM. Cea mai mare valoare a funcției de probabilitate este selectată din toate rulările.
Motivul rezultat este salvat și eliminat din secvențele de intrare pentru a le căuta pe următoarele.
Punctele 1., 2. și 3. se repetă pentru a căuta un anumit număr de motive [8] .

Motivele descoperite la ieșirea programului sunt date sub formă de LOGO .

Timpul de rulare al algoritmului

Algoritmul de căutare a motivelor MEME are loc în pași, unde este o constantă necunoscută (între 10 și 100), este numărul total de litere ale alfabetului dat în secvențele de intrare [9] . Adică, complexitatea algoritmului se dovedește a fi . $W$ $k*W*n^{2)$ $k$ $n$ $O(W*n^{2})$

Avantaje

Spre deosebire de EM, MEME vă permite să lucrați și să găsiți eficient motive în secvențe care conțin mai mult de o copie a unui motiv sau care nu conțin un motiv. Acestea din urmă sunt considerate de algoritm ca zgomot [8] . Un mare plus este, de asemenea, capacitatea de a căuta mai multe motive diferite într-un set de secvențe de intrare [8] și de a căuta un motiv global optim, în timp ce EM se oprește adesea la unul optim local, ceea ce poate să nu fie deloc un motiv [10] ] . Există o implementare a algoritmului sub forma unui program pentru un PC și un server web cu o interfață convenabilă cu un set de programe suplimentare pentru a lucra în continuare cu motivul găsit [9] .

Dezavantaje

Algoritmul MEME recunoaște slab motivele în secvențe lungi, în plus, o lungime mare de secvențe crește foarte mult timpul de rulare al algoritmului [4] [9] . De asemenea, algoritmul MEME face o presupunere de bază importantă despre equiprobabilitatea apariției unui motiv în orice parte a secvenței. Această abordare nu este potrivită pentru căutarea unui motiv în secvențele de ARN , deoarece acestea formează structuri secundare și terțiare, ceea ce face apariția unui motiv mai mult sau mai puțin probabilă în funcție de structură [11] . Algoritmul nu permite găsirea motivelor cu lacune, deoarece însăși formularea problemei algoritmului nu implică căutarea acestora.

Implementarea algoritmului

Pe baza acestui algoritm este implementat instrumentul MEME Suite, disponibil în versiunea web și pentru PC [6] , din 2017 este suportat și actualizat.

Note

↑ Patrik D'haeseleer. Care sunt motivele secvenței ADN? (Engleză) // Nature Biotechnology. - 2006-04-01. — Vol. 24 , iss. 4 . — P. 423–425 . — ISSN 1087-0156 . - doi : 10.1038/nbt0406-423 . Arhivat din original pe 12 aprilie 2017.
↑ 1 2 T. L. Bailey, C. Elkan. Ajustarea unui model de amestec prin maximizarea așteptărilor pentru a descoperi motive în biopolimeri // Proceedings. Conferința internațională privind sistemele inteligente pentru biologie moleculară. — 1994-01-01. - T. 2 . — S. 28–36 . — ISSN 1553-0833 . Arhivat din original pe 24 aprilie 2017.
↑ 1 2 3 4 5 6 7 8 Charles E. Lawrence, Andrew A. Reilly. Un algoritm de maximizare a așteptărilor (EM) pentru identificarea și caracterizarea siturilor comune în secvențe de biopolimeri nealiniate // Proteine: Structură, Funcție și Bioinformatică. — 1990-01-01. — Vol. 7 , iss. 1 . — P. 41–51 . — ISSN 1097-0134 . - doi : 10.1002/prot.340070105 . Arhivat din original pe 15 aprilie 2017.
↑ 1 2 3 4 Timothy L. Bailey, Nadya Williams, Chris Misleh, Wilfred W. Li. MEME: descoperirea și analizarea ADN-ului și a motivelor secvenței proteinelor // Nucleic Acids Research. - 01-07-2006. - T. 34 , nr. suppl_2 . — S. W369–W373 . — ISSN 0305-1048 . doi : 10.1093 / nar/gkl198 . Arhivat din original pe 15 aprilie 2017.
↑ Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant. Suita MEME: instrumente pentru descoperirea și căutarea motivelor // Cercetarea acizilor nucleici. — 2009-07-01. - T. 37 , nr. Problemă cu serverul web . — C. W202–W208 . — ISSN 0305-1048 . - doi : 10.1093/nar/gkp335 . Arhivat din original pe 11 decembrie 2019.
↑ 1 2 3 Introducere - MEME Suite . meme-suite.org. Consultat la 14 aprilie 2017. Arhivat din original pe 26 aprilie 2017. (nedefinit)
↑ Algoritm de maximizare a așteptărilor pentru identificarea site-urilor de legare a proteinelor cu lungimi variabile din fragmente de ADN nealiniate - ScienceDirect . www.sciencedirect.com. Data accesului: 15 aprilie 2017.
↑ 1 2 3 4 5 6 7 8 Timothy L. Bailey, Charles Elkan. Învățare nesupravegheată a mai multor motive în biopolimeri utilizând maximizarea așteptărilor // Învățare automată. — 1995-10-01. — Vol. 21 , iss. 1-2 . — P. 51–80 . - doi : 10.1023/A:1022617714621 .
↑ 1 2 3 Suita MEME - Un set de instrumente pentru găsirea motivelor . Suita MEME . rothlab.ucdavis.edu. Consultat la 14 aprilie 2017. Arhivat din original la 8 februarie 2017. (nedefinit)
↑ A.P. Dempster, N.M. Laird, D.B. Rubin. Probabilitate maximă de la date incomplete prin algoritmul EM // Journal of the Royal Statistical Society. Seria B (Metodologic). — 1977-01-01. - T. 39 , nr. 1 . — S. 1–38 . Arhivat din original pe 19 iulie 2017.
↑ Avinash Achar, Pål Sætrom. Descoperirea motivului ARN: o privire de ansamblu computațională // Biology Direct. — 01-01-2015. - T. 10 . - S. 61 . — ISSN 1745-6150 . - doi : 10.1186/s13062-015-0090-5 .