基于期望最大化的高通量测序数据集模体发现算法研究

摘要

DNA模体发现就是从给定的DNA序列集合中，找到一组相互相似的序列片断，有助于定位转录因子结合位点等调控元件。转录因子可以与基因上游的特定位点相结合，来控制转录起始和转录速率，这些特定位点称为转录因子结合位点。因此，模体发现算法的研究对揭示转录调控机制有着重要的意义。 近些年来，随着高通量测序技术的快速发展，ChIP-seq等技术可以获得全基因组水平上的转录因子结合位点数据，为模体发现提供了大量的实验数据。期望最大化算法被广泛应用于求解模体发现问题，在应对小的数据集时，这些算法通常可以高效且有效的识别出模体，但大数据集为这些算法带来了挑战：如果处理整个数据集，运行时间是不切实际的；如果只处理一个小的样本序列集，则有可能识别不出出现频次较低的模体。针对高通量测序数据集，本文开展了两个部分的工作来设计基于期望最大化的模体发现算法。 第一部分工作利用划分样本集并分别求解的策略提出了MDS3算法。首先将输入序列集划分为多个样本序列集，然后用EM算法求精每个样本序列集中的初始模体，最后将所有样本序列集上的结果进行合并。在对每个样本序列集生成初始模体时，设计了一种能够利用完整输入序列集的方法，有助于识别出现频次较低的模体。实验结果表明，MDS3与现有的算法(MEME-ChIP，F-Motif，PairMotifChIP)的识别准确率相当，并具有更好的时间性能，尤其是对于大的数据集。特别地，当数据集中的模体出现频次较低时，MDS3也具有更好的识别准确率。 第二部分工作基于在线EM设计了一种在线模体发现算法OMD。从给定的输入序列集中不断地获取数据块；对于每个数据块，利用前一个数据块的信息对当前块进行求解；当输入序列集中的所有序列都求解完成后，对结果进行后处理。在对每个数据块进行求解时，将封闭求解(不利用历史数据进行求解的方法)与在线求解(利用历史数据块的求解结果作为先验信息)相结合，可以有效地避免过分依赖于新的数据块。通过实验表明：OMD识别准确率高于现有的在线模体发现算法(EXTREME)；可以有效识别到出现频次较低的模体以及分布不均匀的模体。

目录

第一个书签之前