模體發(fā)現(xiàn)問(wèn)題綜述

1、模體發(fā)現(xiàn)問(wèn)題綜述模體發(fā)現(xiàn)問(wèn)題綜述內(nèi)容概述內(nèi)容概述 問(wèn)題介紹問(wèn)題介紹植入(l,d)模體發(fā)現(xiàn)問(wèn)題的定義給定t條定義于字符集A,T,C,G上的長(zhǎng)度為n的DNA序列，即S=s1,s2,st，以及非負(fù)整數(shù)l和d，0dln。植入(l,d)模體發(fā)現(xiàn)問(wèn)題要找出一個(gè)長(zhǎng)度為l的模體序列x，并非存在于每條輸入序列中，但是對(duì)每條序列而言，至少存在一條子序列xi ，它與x最多有d個(gè)位置差異，即dH(xi,x) d，dH是指兩者之間的海明距離。字符串x稱(chēng)為(l,d)模體， xi稱(chēng)為模體x的實(shí)例。 挑戰(zhàn)實(shí)例挑戰(zhàn)實(shí)例(Challenge Problem,2000)在一組長(zhǎng)度為600個(gè)氨基酸的序列組中，每條序列都包含了一個(gè)長(zhǎng)度

2、為15、不同位數(shù)為4的模式串，要求找出這個(gè)(15,4)模體。該問(wèn)題不適合用概率方法解決，需要用序列匹配的方法查找。問(wèn)題發(fā)展問(wèn)題發(fā)展 擴(kuò)展植入擴(kuò)展植入(l,d)模體發(fā)現(xiàn)模體發(fā)現(xiàn)問(wèn)題（問(wèn)題（EMP，2004）給定t條長(zhǎng)度為n的輸入序列，其中每條序列包含長(zhǎng)度為l的模體M的0個(gè)或多個(gè)植入(l,d)實(shí)例。要求在不知道長(zhǎng)度l和植入實(shí)例位置的情況下，找出M。 模模體詞干搜索體詞干搜索(motif stem search,2010)模體詞干是指一個(gè)長(zhǎng)度為l的可能包含通配符的字符串，代表了一個(gè)候選模體集。假設(shè)DNA模體為A*GT，*代表一個(gè)通配符，那么候選模體有AAGT,ATGT,AGGT,ACGT。MSS問(wèn)題

3、就是要找到一個(gè)模體詞干集合，它包含了全部可能的(l,d)模體。植入(l,d)模體發(fā)現(xiàn)算法介紹(2012)并行算法介紹 cuda-MEME(2009)利用基于GPU的CUDA技術(shù)，在起始位置搜索階段進(jìn)行并行化，再執(zhí)行MEME算法。 A hybrid method(2012)將算法分為兩部分：在前q條序列中使用一種精確算法，生成候選模體集；用模式匹配方法在剩余序列中驗(yàn)證模體。使用openMP。 PMSPMR(2012)基于PMSP算法，采用合適的數(shù)據(jù)劃分方法，使用MapReduce并行化。A hybrid method(2012) 基于PMSprune算法思想改進(jìn) 將算法分為候選模體的生成和模體的

4、驗(yàn)證兩部分精確算法+序列匹配算法 具有可集成性的特點(diǎn) 解決了較大的挑戰(zhàn)實(shí)例(21,8)問(wèn)題 PMSPMR算法算法描述描述給定t條定義于字符集A, C, G, T上的長(zhǎng)度為n的DNA序列，即S=s1, s2, , st，以及長(zhǎng)度為l字符串M和非負(fù)整數(shù)d，Bd(M)表示候選模體集，0dln。計(jì)算s1中所有長(zhǎng)度為l的字串x，并將每條子串與s2到st中長(zhǎng)度為l的字串y進(jìn)行對(duì)比，若dH(x,y) 2d,則記錄所有yi，最后，若Bd(M)中存在z，使得dH(z,yi) d，則yi記為模體M的實(shí)例。算法與數(shù)據(jù)算法與數(shù)據(jù)PMSPMR算法描述Map函數(shù)：函數(shù)：PMSPMR算法描述Reduce函數(shù)：函數(shù)：數(shù)據(jù)劃分

5、方法（一）數(shù)據(jù)劃分方法（一）數(shù)據(jù)劃分方法（二）數(shù)據(jù)劃分方法（二）數(shù)據(jù)劃分方法（三）數(shù)據(jù)劃分方法（三）數(shù)據(jù)來(lái)源數(shù)據(jù)來(lái)源 模擬數(shù)據(jù)模擬數(shù)據(jù)常用的數(shù)據(jù)情況是：在各堿基等概率出現(xiàn)的情況下，隨機(jī)生成t條長(zhǎng)為n的序列和一個(gè)長(zhǎng)為l的模體m。對(duì)于每條序列，隨機(jī)生成一個(gè)m的實(shí)例植入到序列中。t=20，n=600。 真實(shí)的生物數(shù)據(jù)真實(shí)的生物數(shù)據(jù)對(duì)于真實(shí)的生物數(shù)據(jù)，使用PMSPMR查找序列中的已知轉(zhuǎn)錄調(diào)控元件，以驗(yàn)證PMSPMR算法對(duì)真實(shí)數(shù)據(jù)的有效性。運(yùn)行時(shí)間比較運(yùn)行時(shí)間比較評(píng)價(jià)方法 性能系數(shù)性能系數(shù)(performance coefficient, nPC)nPC=nTP/(nTP+nFN+nFP) nTP表示檢測(cè)出的模體與真實(shí)模體重合的堿基的位數(shù)；nFN表示真實(shí)模體中