MEME

Multiple EM for Motif Elicitation ( MEME ) er en algoritme og et værktøj af samme navn, som er en implementering af algoritmen, til at søge efter motiver i biologiske sekvenser af proteiner og DNA . Algoritmen er baseret på gentagen anvendelse af maximum likelihood - metoden . Et motiv er en kort sekvens af nukleotider eller aminosyrer, der er fælles for nogle sæt sekvenser.

Søgen efter motiver er en vigtig opgave i biologien, eftersom tilstedeværelsen af et motiv i en sekvens kan tjene som et signal til sekvensgenkendelse for transkriptionsfaktorer eller restriktionsendonukleaser [1] .

Historie

MEME-algoritmen blev udviklet i 1994 af Timothy Bailey og Charles Elkan [2] . Det er en udvidelse af den maksimale sandsynlighed metode til at finde motiver , som blev offentliggjort i 1990 af Lawrence og Reilly [3] . Den oprindelige metode gjorde det muligt kun at finde ét motiv i et sæt af sekvenser, og dette motiv var lokalt optimalt, da algoritmen i høj grad afhænger af valget af startparametre. Rigtigheden af dens drift afhang også stærkt af støjniveauet i de betragtede sekvenser. MEME-metoden gjorde det muligt at omgå disse mangler. I 1996 blev der oprettet en webserver indeholdende en implementering af MEME, som blev brugt af omkring 800 unikke besøgende mellem 2000 og 2006 [4] . Og i 2009 blev MEME Suite-pakken præsenteret, der ikke kun indeholdt implementeringen af MEME, men også mange andre relaterede programmer [5] . I alt har følgende personer arbejdet på skabelsen af MEME Suiten: Timothy Bailey, William Stafford Nobel, Charles Elkan og Michael Gribskov bidrog også til projektet. Fra 2017 er MEME Suiten understøttet af et NIH -bevilling , og webserveren modtager også hjælp fra Google og Amazon [6] .

Udtalelse af problemet

Det er nødvendigt at identificere et eller flere almindelige motiver i et sæt af forkert justerede nukleotid- eller aminosyresekvenser, der hver indeholder et, flere eller ingen motiver. I dette tilfælde betragter vi motiver uden huller (huller), der har en fælles biologisk funktion. For eksempel kan de være mål for et enkelt DNA-bindende protein. MEME bruger repræsentationen af et biologisk motiv i form af en position-vægt matrix (PWM) [2] .

Forberedende fase

Forberedelse af sekvenser

Det er ikke muligt at detektere et fælles motiv i noget sæt af sekvenser, derfor, for at algoritmen skal fungere korrekt, skal sekvenser vælges omhyggeligt og forberedes: et fælles motiv skal forventes i dette sæt (f.eks. vides sekvenser at binde til en enkelt transkriptionsfaktor ), og sekvenserne skal være så korte, at så vidt muligt (ideelt set <1000 nukleotider ) [4] .

Valg af inputparametre

Som standard indeholder MEME-outputtet ikke mere end tre motiver med længde fra 6 til 50, der findes både på den fremadgående og omvendte kæde af inputsekvenser [6] . Hvis den biologiske betydning af søgeobjekterne er kendt, så kan man gætte og indstille antallet og længden af motiver, der forventes i dette sæt af sekvenser. Dette vil forbedre kvaliteten af forudsigelsen i tilfælde af, at motivet ikke passer til standardparametrene [4] .

Algoritme

EM-algoritme til at finde sekvenser

Indgangen til EM-algoritmen er:

et sæt sekvenser, der hører til alfabetet ; $L$
længden af det påståede motiv [3] . $W$

Algoritmen returnerer en mulig model af det fundne motiv [3] .

Ved hvert trin i algoritmen bestemmes motivet af en positionsvægtmatrix (PWM) af størrelse , hvor er størrelsen af alfabetet. Hver celle i PVM'en har en vægt , der afhænger af sandsynligheden for, at et bogstav optræder i kolonnen , hvor . Disse værdier genberegnes under hver iteration af algoritmen [3] . $|L|\ gange W$ $|L|$ ${\displaystyle p_{lc))$ $l$ $c$ $1\leq c\leq W$

Da det i starten er ukendt, hvor præcist i sekvenserne motivet er placeret, beregnes ved hvert trin i algoritmen værdierne af matricen , hvor matrixelementet er sandsynligheden for, at motivet begynder i sekvensen fra position [3 ] . $Z$ $z_{{ij}}$ $jeg$ $j$

Algoritmen består således af følgende sekvens af trin:

Den indledende PVM af motivet er taget. Det kan gives eller vælges tilfældigt.
Baseret på de tilgængelige SMP-værdier for hver position i hver sekvens, beregnes matrixværdierne ved hjælp af logaritmen for sandsynlighedsfunktionen : ${\displaystyle p_{lc))$ $Z$ log ⁡ ( l jeg k e l jeg h o o d ) = N ∑ j = en W ∑ l ∈ L f l j log ⁡ ( s l j ) + N ( K − W ) ∑ l ∈ L f l 0 log ⁡ ( s l 0 ) + N log ⁡ ( en K − W + en ) , {\displaystyle \log(sandsynlighed)=N\sum _{j=1}^{W}\sum _{l\in L}f_{lj}\log(p_{lj})+N(KW)\sum _{l\in L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),} $\log(sandsynlighed)=N\sum _{j=1}^{W}\sum _{l\in L}f_{lj}\log(p_{lj})+N(KW)\sum _{l\in L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),$ hvor er antallet af inputsekvenser, er længden af inputsekvenserne, er længden af motivet, er alfabetet, er sandsynligheden for at et bogstav optræder i motivpositionen, er sandsynligheden for at bogstavet optræder i en hvilken som helst position, er den observerede frekvens af bogstavet i motivpositionen, er den observerede frekvens af bogstavet i enhver position . $N$ $K$ $W$ $L$ $p_{lj}$ $l$ $j$ $p_{l0}$ $l$ ${\displaystyle f_{lj))$ $l$ $j$ ${\displaystyle f_{l0))$ $l$
For hver sekvens vælges maksimum af sandsynlighedsfunktionen fra matrixen, og positionen i sekvensen svarende til dette maksimum bestemmes. Justering er bygget i henhold til de tilsvarende positioner, nye værdier af PWM beregnes i henhold til forekomsten af bogstaver i de ønskede kolonner af motivet [3] . $Z$
Punkt 2. og 3. gentages, indtil ændringerne i PVM'ens værdier bliver mindre end den oprindeligt indstillede tærskel [3] .

Beregning af de bedste inputparametre for MEME-algoritmen

For at forbedre resultatet af EM-algoritmen er det nødvendigt at vælge det rigtige sæt startparametre. Der er flere måder at gøre dette på:

Kør algoritmen med forskellige mulige vilkårlige input, og vælg derefter dem, hvor sandsynlighedsfunktionen vil være størst. Denne tilgang forbedrer kvaliteten af forudsigelsen, men garanterer ikke et bedre resultat [3] [7] .
Brug efterfølgemetoden [8] .

Underfølgemetoden er baseret på, at det ønskede motiv skal svare til en eller anden længdefølge i de originale data. For hver sådan undersekvens konstrueres PVM'er, hvorfra hver lancering af EM-algoritmen starter. Den største værdi af sandsynlighedsfunktionen blandt alle kørsler af algoritmen vil være det globale maksimum og vil give det ønskede motiv. Det er dette princip, der begrænser søgen efter motiver med huller [8] . $W$

Ifølge en given undersekvens kan en PSM konstrueres på forskellige måder. MEME-algoritmen bruger følgende: frekvensen af bogstavet svarende til bogstavet i efterfølgen tages som , algoritmen fungerer bedst for . Og sandsynligheden for alle andre bogstaver tages som [8] . $0<X<1$ $0{,}4\leq X\leq 0{,}8$ ${\frac {1-X}{|L|-1}}$

Det viser sig, at i det øjeblik, hvor algoritmen køres for en undersekvens svarende til det korrekte motiv, konvergerer EM-algoritmen så hurtigt, at en iteration er nok. For at spare tid er det derfor nok kun at køre én iteration af EM-algoritmen hver gang, som er implementeret i MEME-algoritmen [8] .

MEME-algoritme

MEME-algoritmen er baseret på gentagen anvendelse af EM-algoritmen til at søge efter et motiv i sekvenser. Indgangen til MEME-algoritmen er:

et sæt sekvenser, der hører til alfabetet ; $L$
længden af det påståede motiv ; $W$
det forventede antal kopier af motivet;
antallet af forskellige motiver [8] .

EM-algoritmen er modificeret til følgende:

De indledende parametre vælges af den efterfølgende metode.
For hvert sæt af inputparametre udføres en iteration af EM-algoritmen. Den største værdi af sandsynlighedsfunktionen vælges fra alle kørsler.
Det resulterende motiv gemmes og fjernes fra inputsekvenserne for at søge efter de næste.
Punkt 1., 2. og 3. gentages for at søge efter et givet antal motiver [8] .

De opdagede motiver ved programmets output er givet i form af LOGO .

Køretid for algoritmen

MEME længde motivsøgningsalgoritmen tager trin, hvor er en ukendt konstant (mellem 10 og 100), er det samlede antal bogstaver i det givne alfabet i inputsekvenserne [9] . Det vil sige, at kompleksiteten af algoritmen viser sig at være . $W$ ${\displaystyle k*W*n^{2))$ $k$ $n$ $O(W*n^{2})$

Fordele

I modsætning til EM giver MEME dig mulighed for at arbejde og effektivt finde motiver i sekvenser, der indeholder mere end én kopi af et motiv eller ikke indeholder et motiv. Sidstnævnte betragtes af algoritmen som støj [8] . Et stort plus er også muligheden for at søge efter flere forskellige motiver i ét sæt inputsekvenser [8] og søge efter et globalt optimalt motiv, mens EM ofte stopper ved et lokalt optimalt, hvilket måske slet ikke er et motiv [10 ] . Der er en implementering af algoritmen i form af et program til en pc og en webserver med en bekvem grænseflade med et sæt ekstra programmer til videre arbejde med det fundne motiv [9] .

Ulemper

MEME-algoritmen genkender dårligt motiver i lange sekvenser, desuden øger en stor længde af sekvenser algoritmens køretid kraftigt [4] [9] . MEME-algoritmen gør også en vigtig grundlæggende antagelse om ligesandsynligheden for forekomsten af et motiv i en hvilken som helst del af sekvensen. Denne tilgang er ikke egnet til at søge efter et motiv i RNA- sekvenser , da de danner sekundære og tertiære strukturer, hvilket gør udseendet af et motiv mere eller mindre sandsynligt afhængigt af strukturen [11] . Algoritmen tillader ikke at finde motiver med huller, da selve formuleringen af problemet med algoritmen ikke indebærer at søge efter dem.

Implementering af algoritmen

Baseret på denne algoritme er MEME Suite-værktøjet implementeret, tilgængeligt i webversionen og til pc [6] , fra 2017 er det understøttet og opdateret.

Noter

↑ Patrik D'haeseleer. Hvad er DNA-sekvensmotiver? (engelsk) // Nature Biotechnology. - 2006-04-01. — Bd. 24 , udg. 4 . — S. 423–425 . — ISSN 1087-0156 . - doi : 10.1038/nbt0406-423 . Arkiveret fra originalen den 12. april 2017.
↑ 1 2 T. L. Bailey, C. Elkan. Tilpasning af en blandingsmodel ved forventningsmaksimering for at opdage motiver i biopolymerer // Proceedings. International konference om intelligente systemer til molekylærbiologi. — 1994-01-01. - T. 2 . — S. 28–36 . — ISSN 1553-0833 . Arkiveret fra originalen den 24. april 2017.
↑ 1 2 3 4 5 6 7 8 Charles E. Lawrence, Andrew A. Reilly. En forventningsmaksimeringsalgoritme (EM) til identifikation og karakterisering af fælles steder i ikke-alignede biopolymersekvenser // Proteins: Structure, Function, and Bioinformatics. — 1990-01-01. — Bd. 7 , iss. 1 . — S. 41–51 . — ISSN 1097-0134 . - doi : 10.1002/prot.340070105 . Arkiveret fra originalen den 15. april 2017.
↑ 1 2 3 4 Timothy L. Bailey, Nadya Williams, Chris Misleh, Wilfred W. Li. MEME: opdagelse og analyse af DNA- og proteinsekvensmotiver // Nukleinsyreforskning. - 2006-07-01. - T. 34 , no. suppl_2 . — S. W369–W373 . — ISSN 0305-1048 . doi : 10.1093 / nar/gkl198 . Arkiveret fra originalen den 15. april 2017.
↑ Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant. MEME Suite: værktøjer til motivopdagelse og -søgning // Nucleic Acids Research. — 2009-07-01. - T. 37 , no. Webserver problem . — C. W202–W208 . — ISSN 0305-1048 . - doi : 10.1093/nar/gkp335 . Arkiveret fra originalen den 11. december 2019.
↑ 1 2 3 Introduktion - MEME Suite . meme-suite.org. Hentet 14. april 2017. Arkiveret fra originalen 26. april 2017. (ubestemt)
↑ Forventningsmaksimeringsalgoritme til identifikation af proteinbindingssteder med variable længder fra ikke-justerede DNA-fragmenter - ScienceDirect . www.sciencedirect.com. Dato for adgang: 15. april 2017.
↑ 1 2 3 4 5 6 7 8 Timothy L. Bailey, Charles Elkan. Uovervåget læring af flere motiver i biopolymerer ved hjælp af forventningsmaksimering // Machine Learning. — 1995-10-01. — Bd. 21 , udg. 1-2 . — S. 51–80 . - doi : 10.1023/A:1022617714621 .
↑ 1 2 3 MEME Suite - Et sæt værktøjer til at finde motiver . MEME Suiten . rothlab.ucdavis.edu. Hentet 14. april 2017. Arkiveret fra originalen 8. februar 2017. (ubestemt)
↑ A.P. Dempster, N.M. Laird, D.B. Rubin. Maximum Likelihood fra ufuldstændige data via EM Algorithm // Journal of the Royal Statistical Society. Serie B (metodologisk). — 1977-01-01. - T. 39 , no. 1 . — S. 1–38 . Arkiveret fra originalen den 19. juli 2017.
↑ Avinash Achar, Pål Sætrom. Opdagelse af RNA-motiv: et beregningsmæssigt overblik // Biology Direct. — 2015-01-01. - T. 10 . - S. 61 . — ISSN 1745-6150 . - doi : 10.1186/s13062-015-0090-5 .