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

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

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

4、驗證兩部分精確算法+序列匹配算法 具有可集成性的特點 解決了較大的挑戰(zhàn)實例(21,8)問題 PMSPMR算法算法描述描述給定t條定義于字符集A, C, G, T上的長度為n的DNA序列，即S=s1, s2, , st，以及長度為l字符串M和非負(fù)整數(shù)d，Bd(M)表示候選模體集，0dln。計算s1中所有長度為l的字串x，并將每條子串與s2到st中長度為l的字串y進行對比，若dH(x,y) 2d,則記錄所有yi，最后，若Bd(M)中存在z，使得dH(z,yi) d，則yi記為模體M的實例。算法與數(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ù)來源數(shù)據(jù)來源 模擬數(shù)據(jù)模擬數(shù)據(jù)常用的數(shù)據(jù)情況是：在各堿基等概率出現(xiàn)的情況下，隨機生成t條長為n的序列和一個長為l的模體m。對于每條序列，隨機生成一個m的實例植入到序列中。t=20，n=600。 真實的生物數(shù)據(jù)真實的生物數(shù)據(jù)對于真實的生物數(shù)據(jù)，使用PMSPMR查找序列中的已知轉(zhuǎn)錄調(diào)控元件，以驗證PMSPMR算法對真實數(shù)據(jù)的有效性。運行時間比較運行時間比較評價方法 性能系數(shù)性能系數(shù)(performance coefficient, nPC)nPC=nTP/(nTP+nFN+nFP) nTP表示檢測出的模體與真實模體重合的堿基的位數(shù)；nFN表示真實模體中