Metoder for å akselerere MEME

Abstract

MEME er et mye brukt verktøy for å finne nye mønster i biologiske data, og bruker Expectation Maximation på PWM-er for å finne mønster som skiller seg mest mulig fra bakgrunnen. Siden Expectation Maximation er en algoritme som konvergerer raskt mot lokalt maksima, må MEME finne gode startpunkt for EM som har en stor sjanse for å ende opp i det globalt maksimum. Det gjøre MEME ved å kjøre en iterasjon av EM med PWM-er generert fra hver mulig subsekvens i datasettet. Slike søk tar tid, og MEME bruker lang tid på store datasett. Ved å akselerere MEME, vil vi kunne bruke det på større datasett, og akselerasjon kan også bidra til å gjøre et grundigere søk etter startpunkt slik at man er sikrere på å ende opp i det globale maksimum. For å hjelpe oss med disse søkene ser vi på teknikker som innebærer hardwareakselerering og andre algoritmer for PWM-matching i software.