MEME

Multiple EM for Motif Elicitation ( MEME ) on samanniminen algoritmi ja työkalu, joka on algoritmin toteutus motiivien etsimiseen proteiinien ja DNA :n biologisista sekvensseistä . Algoritmi perustuu suurimman todennäköisyyden menetelmän toistuvaan soveltamiseen . Motiivi on lyhyt nukleotidien tai aminohappojen sekvenssi , joka on yhteinen jollekin sekvenssijoukolle.

Motiivien etsiminen on tärkeä tehtävä biologiassa, koska motiivin läsnäolo sekvenssissä voi toimia signaalina transkriptiotekijöiden tai restriktioendonukleaasien sekvenssin tunnistamiselle [1] .

Historia

MEME-algoritmin kehittivät vuonna 1994 Timothy Bailey ja Charles Elkan [2] . Se on laajennus suurimman todennäköisyyden menetelmälle motiivien löytämiseksi , jonka Lawrence ja Reilly julkaisivat vuonna 1990 [3] . Alkuperäinen menetelmä mahdollisti vain yhden motiivin löytämisen sekvenssijoukosta, ja tämä motiivi oli paikallisesti optimaalinen, koska algoritmi riippuu voimakkaasti aloitusparametrien valinnasta. Sen toiminnan oikeellisuus riippui myös vahvasti kohinatasosta tarkasteluissa jaksoissa. MEME-menetelmä mahdollisti näiden puutteiden kiertämisen. Vuonna 1996 luotiin MEME-toteutuksen sisältävä web-palvelin, jota käytti noin 800 yksilöllistä kävijää vuosina 2000-2006 [4] . Ja vuonna 2009 esiteltiin MEME Suite -paketti, joka sisältää MEME:n toteutuksen lisäksi monia muita siihen liittyviä ohjelmia [5] . Yhteensä seuraavat ihmiset työskentelivät MEME Suiten luomisessa: Timothy Bailey, William Stafford Nobel, Charles Elkan ja Michael Gribskov osallistuivat myös projektiin. Vuodesta 2017 lähtien MEME Suitea tuetaan NIH :n apurahalla , ja verkkopalvelin saa apua myös Googlelta ja Amazonilta [6] .

Ongelman selvitys

On välttämätöntä tunnistaa yksi tai useampi yleinen motiivi väärin kohdistettujen nukleotidi- tai aminohapposekvenssien joukosta, joista jokainen sisältää yhden, useamman tai ei yhtään motiivia. Tässä tapauksessa tarkastellaan motiiveja ilman aukkoja (aukoja), joilla on yhteinen biologinen tehtävä. Ne voivat esimerkiksi olla yhden DNA:ta sitovan proteiinin kohteita. MEME käyttää biologisen motiivin esitystä paikka -painomatriisin (PWM) muodossa [2] .

Valmisteluvaihe

Valmistellaan jaksoja

Yhteistä motiivia ei ole mahdollista havaita mistään sekvenssijoukosta, joten jotta algoritmi toimisi oikein, sekvenssit on valittava ja valmisteltava huolellisesti: tässä sarjassa on odotettava yhteinen motiivi (esim. sekvenssien tiedetään sitoutuvan yhdelle transkriptiotekijälle ), ja sekvenssien tulee olla niin lyhyitä, että mahdollisimman pitkälle (ihannetapauksessa <1000 nukleotidia ) [4] .

Syöttöparametrien valinta

Oletusarvoisesti MEME-tulostus sisältää enintään kolme motiivia, joiden pituus on 6-50 ja jotka löytyvät sekä syöttösekvenssien myötä- että taaksepäin [6] . Jos hakuobjektien biologinen merkitys tiedetään, voidaan arvata ja asettaa motiivien lukumäärä ja pituus, joita tässä sekvenssijoukossa odotetaan. Tämä parantaa ennusteen laatua, jos motiivi ei sovi oletusparametreihin [4] .

Algoritmi

EM-algoritmi sekvenssien etsimiseen

EM-algoritmin syöte on:

joukko aakkosiin kuuluvia sekvenssejä ; $L$
väitetyn motiivin pituus [3] . $W$

Algoritmi palauttaa mahdollisen mallin löydetystä motiivista [3] .

Algoritmin jokaisessa vaiheessa motiivi määräytyy sijainti-painomatriisin (PWM) avulla, jonka koko on , jossa on aakkosten koko. Jokaisella PVM:n solulla on painoarvo , joka riippuu todennäköisyydestä, että kirjain ilmestyy sarakkeeseen , jossa . Nämä arvot lasketaan uudelleen jokaisen algoritmin iteraation aikana [3] . $|L|\times W$ $|L|$ ${\displaystyle p_{lc))$ $l$ $c$ $1\leq c\leq W$

Koska aluksi ei tiedetä, missä sekvenssissä tarkalleen motiivi sijaitsee, algoritmin jokaisessa vaiheessa lasketaan matriisin arvot , jossa matriisielementti on todennäköisyys, että motiivi alkaa sekvenssissä paikasta [3 ] . $Z$ $z_{{ij}}$ $i$ $j$

Siten algoritmi koostuu seuraavista vaiheista:

Motiivin alkuperäinen PVM otetaan. Se voidaan antaa tai valita satunnaisesti.
Matriisiarvot lasketaan kunkin sekvenssin kullekin asemalle saatavilla olevien SMP-arvojen perusteella käyttämällä todennäköisyysfunktion logaritmia : ${\displaystyle p_{lc))$ $Z$ Hirsi ⁡ ( l i k e l i h o o d ) = N ∑ j = yksi W ∑ l ∈ L f l j Hirsi ⁡ ( s l j ) + N ( K − W ) ∑ l ∈ L f l 0 Hirsi ⁡ ( s l 0 ) + N Hirsi ⁡ ( yksi K − W + yksi ) , {\displaystyle \log(likelihood)=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(likelihood)=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))),$ missä on syöttösekvenssien lukumäärä, on syöttösekvenssien pituus, on motiivin pituus, on aakkoset, on todennäköisyys sille, että kirjain ilmestyy aihekohtaan, on todennäköisyys, että kirjain esiintyy missä tahansa kohdassa, on kirjaimen havaittu taajuus motiiviasemassa , on kirjaimen havaittu taajuus missä tahansa asennossa . $N$ $K$ $W$ $L$ $p_{lj}$ $l$ $j$ $p_{l0}$ $l$ ${\displaystyle f_{lj))$ $l$ $j$ ${\displaystyle f_{l0))$ $l$
Jokaiselle sekvenssille valitaan matriisista todennäköisyysfunktion maksimi ja määritetään tätä maksimia vastaava paikka sekvenssissä. Kohdistus rakennetaan vastaavien paikkojen mukaan, PWM:n uudet arvot lasketaan kirjaimien esiintymisen mukaan motiivin halutuissa sarakkeissa [3] . $Z$
Pisteitä 2. ja 3. toistetaan, kunnes PVM:n arvojen muutokset tulevat pienemmiksi kuin alun perin asetettu kynnys [3] .

MEME-algoritmin parhaiden syöttöparametrien laskeminen

EM-algoritmin tuloksen parantamiseksi on tarpeen valita oikea aloitusparametrisarja. Voit tehdä tämän useilla tavoilla:

Suorita algoritmi useilla mahdollisilla mielivaltaisilla syötteillä ja valitse sitten ne, joiden todennäköisyysfunktio on suurin. Tämä lähestymistapa parantaa ennusteen laatua, mutta ei takaa parempaa tulosta [3] [7] .
Käytä osasekvenssimenetelmää [8] .

Osasekvenssimenetelmä perustuu siihen, että halutun motiivin tulee vastata jotakin pituuden osajaksoa alkuperäisessä tiedossa. Jokaiselle tällaiselle osasekvenssille rakennetaan PVM:t, joista jokainen EM-algoritmin käynnistys alkaa. Suurin todennäköisyysfunktion arvo algoritmin kaikista ajoista on globaali maksimi ja antaa halutun motiivin. Juuri tämä periaate rajoittaa motiivien etsimistä aukoilla [8] . $W$

Tietyn osasekvenssin mukaan PSM voidaan rakentaa eri tavoin. MEME-algoritmi käyttää seuraavaa: osajonon kirjainta vastaavan kirjaimen taajuudeksi otetaan , algoritmi toimii parhaiten . Ja kaikkien muiden kirjainten todennäköisyydet ovat [8] . $0<X<1$ $0{,}4\leq X\leq 0{,}8$ ${\frac {1-X}{|L|-1}}$

Osoittautuu, että oikeaa motiivia vastaavan osasekvenssin algoritmia ajettaessa EM-algoritmi konvergoi niin nopeasti, että yksi iteraatio riittää. Siksi ajan säästämiseksi riittää, että kulloinkin suoritetaan vain yksi iteraatio EM-algoritmista, joka on toteutettu MEME-algoritmissa [8] .

MEME-algoritmi

MEME-algoritmi perustuu EM-algoritmin toistuvaan soveltamiseen motiivin etsimiseen sekvensseistä. MEME-algoritmin syöte on:

joukko aakkosiin kuuluvia sekvenssejä ; $L$
väitetyn motiivin pituus ; $W$
aiheen odotettu kopioiden lukumäärä;
eri motiivien määrä [8] .

EM-algoritmi muutetaan seuraavasti:

Alkuparametrit valitaan osasekvenssimenetelmällä.
Jokaiselle syöttöparametrijoukolle suoritetaan yksi EM-algoritmin iteraatio. Todennäköisyysfunktion suurin arvo valitaan kaikista ajoista.
Tuloksena oleva motiivi tallennetaan ja poistetaan syöttösekvensseistä seuraavien etsimistä varten.
Kohteet 1., 2. ja 3. toistetaan etsimään tietty määrä motiiveja [8] .

Ohjelman lähdöstä löydetyt aiheet on annettu LOGO :n muodossa .

Algoritmin ajoaika

MEME-pituuden motiivihakualgoritmi ottaa askeleita, missä on tuntematon vakio (välillä 10 ja 100), on syötesarjoissa olevien aakkosten kirjainten kokonaismäärä [9] . Eli algoritmin monimutkaisuus osoittautuu . $W$ ${\displaystyle k*W*n^{2))$ $k$ $n$ $O(W*n^{2})$

Edut

Toisin kuin EM, MEME antaa sinun työskennellä ja löytää tehokkaasti motiiveja sekvensseistä, jotka sisältävät useamman kuin yhden kopion motiivista tai eivät sisällä motiivia. Algoritmi pitää jälkimmäisiä kohina [8] . Iso plussa on myös kyky etsiä useita eri motiiveja yhdestä syöttösekvenssijoukosta [8] ja etsiä globaalia optimaalista motiivia, kun taas EM pysähtyy usein paikallisesti optimaaliseen motiiviin, mikä ei välttämättä ole motiivi [10] ] . Algoritmi on toteutettu PC-ohjelman ja web-palvelimen muodossa, jossa on kätevä käyttöliittymä lisäohjelmien kanssa jatkotyöskentelyä varten löydetyn motiivin kanssa [9] .

Haitat

MEME-algoritmi tunnistaa huonosti pitkien sekvenssien motiivit, lisäksi suuri sekvenssien pituus pidentää huomattavasti algoritmin ajoaikaa [4] [9] . Lisäksi MEME-algoritmi tekee tärkeän perusoletuksen motiivin esiintymisen yhtäläisyydestä missä tahansa sekvenssin osassa. Tämä lähestymistapa ei sovellu motiivien etsimiseen RNA -sekvensseistä , koska ne muodostavat sekundaarisia ja tertiäärisiä rakenteita, mikä tekee motiivin ilmaantumisen enemmän tai vähemmän todennäköiseksi rakenteesta riippuen [11] . Algoritmi ei salli motiivien löytämistä aukoista, koska algoritmin ongelman muotoilu ei tarkoita niiden etsimistä.

Algoritmin toteutus

Tämän algoritmin perusteella on toteutettu MEME Suite -työkalu, joka on saatavana verkkoversiona ja PC:lle [6] , vuodesta 2017 lähtien sitä tuetaan ja päivitetään.

Muistiinpanot

↑ Patrik D'haeseer. Mitä ovat DNA-sekvenssimotiivit? (englanniksi) // Nature Biotechnology. - 01.04.2006. — Voi. 24 , iss. 4 . — s. 423–425 . — ISSN 1087-0156 . - doi : 10.1038/nbt0406-423 . Arkistoitu alkuperäisestä 12. huhtikuuta 2017.
↑ 1 2 T. L. Bailey, C. Elkan. Seosmallin sovittaminen odotusten maksimoinnilla motiivien löytämiseksi biopolymeereistä // Proceedings. Molekyylibiologian älykkäitä järjestelmiä käsittelevä kansainvälinen konferenssi. - 1994-01-01. - T. 2 . - S. 28-36 . — ISSN 1553-0833 . Arkistoitu alkuperäisestä 24. huhtikuuta 2017.
↑ 1 2 3 4 5 6 7 8 Charles E. Lawrence, Andrew A. Reilly. Odotuksen maksimointialgoritmi (EM) yhteisten kohtien tunnistamiseen ja karakterisointiin kohdistamattomissa biopolymeerisekvensseissä // Proteiinit: rakenne, toiminta ja bioinformatiikka. - 1990-01-01. — Voi. 7 , iss. 1 . – s. 41–51 . — ISSN 1097-0134 . - doi : 10.1002/prot.340070105 . Arkistoitu alkuperäisestä 15. huhtikuuta 2017.
↑ 1 2 3 4 Timothy L. Bailey, Nadya Williams, Chris Misleh, Wilfred W. Li. MEME: DNA- ja proteiinisekvenssimotiivien löytäminen ja analysointi // Nucleic Acids Research. - 01.07.2006. - T. 34 , no. suppl_2 . – S. W369–W373 . — ISSN 0305-1048 . doi : 10.1093 / nar/gkl198 . Arkistoitu alkuperäisestä 15. huhtikuuta 2017.
↑ Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant. MEME Suite: työkalut motiivien löytämiseen ja etsimiseen // Nucleic Acids Research. - 01-07-2009 - T. 37 , no. Verkkopalvelimen ongelma . — C. W202–W208 . — ISSN 0305-1048 . - doi : 10.1093/nar/gkp335 . Arkistoitu alkuperäisestä 11. joulukuuta 2019.
↑ 1 2 3 Johdanto - MEME Suite . meme-suite.org. Haettu 14. huhtikuuta 2017. Arkistoitu alkuperäisestä 26. huhtikuuta 2017. (määrätön)
↑ Odotuksen maksimointialgoritmi eripituisten proteiinia sitovien kohtien tunnistamiseen kohdistamattomista DNA-fragmenteista - ScienceDirect . www.sciencedirect.com. Käyttöönottopäivä: 15.4.2017.
↑ 1 2 3 4 5 6 7 8 Timothy L. Bailey, Charles Elkan. Ohjaamaton oppiminen useista motiiveista biopolymeereissä käyttämällä odotusten maksimointia // Koneoppiminen. - 1995-10-01. — Voi. 21 , iss. 1-2 . — s. 51–80 . - doi : 10.1023/A:1022617714621 .
↑ 1 2 3 MEME Suite - työkalusarja aiheiden etsimiseen . MEME-sviitti . rothlab.ucdavis.edu. Haettu 14. huhtikuuta 2017. Arkistoitu alkuperäisestä 8. helmikuuta 2017. (määrätön)
↑ A.P. Dempster, N.M. Laird, D.B. Rubin. Suurin todennäköisyys epätäydellisistä tiedoista EM-algoritmin kautta // Journal of the Royal Statistical Society. Sarja B (Metodologinen). - 1977-01-01. - T. 39 , no. 1 . - S. 1-38 . Arkistoitu alkuperäisestä 19. heinäkuuta 2017.
↑ Avinash Achar, Pål Sætrom. RNA-motiivien löytö: laskennallinen yleiskatsaus // Biology Direct. – 1.1.2015. - T. 10 . - S. 61 . — ISSN 1745-6150 . - doi : 10.1186/s13062-015-0090-5 .