En maskinvareakselerert parallell gibbs-sampler for oppdaging av motiver

Abstract

Store mengder genomisk data er idag tilgjengelig i digital form, og utvikling av teknikker for analyse av dette materialet er et viktig forskningsfelt. Oppdaging av overrepresenterte mønster er et av målene for slik analyse. Ved å identifisere slike mønster kan man få bedre forståelse for de komplekse mekanismene som styrer basisfunksjonene i biologiske prosesser. Flere metoder for oppdaging av overrepresenterte mønster er utviklet, deriblant gibbs-sampling som baserer seg på en Position Weight Matrix(PWM)-representasjon av mønstrene. Den har vist seg å gi en god balanse mellom pålitelighet og hastighet. Gibbs-sampling er ikke-deterministisk og må kjøres flere ganger på datamaterialet for å gi gode resultater. Den er også sekvensiell i sin natur, og egner seg derfor i utgangspunktet dårlig for parallellisering. I denne rapporten presenteres endringer i algoritmen som muliggjør parallell kjøring og bruk av spesialmaskinvare for PWM-operasjoner. To strategier for parallellisering blir undersøkt, og begge gir en betydelig hastighetsøkning i forhold til en sekvensiell implementasjon.