生物序列大数据集模体发现算法的研究

Motif discovery plays an important role in locating significant sequence segments in biological sequences. The exact algorithms for motif discovery can report the optimal motif under a specified measure. In recent years, the large biological sequence datasets bring new challenges to the exact algorithms in the aspect of time performance. Aimed at designing efficient exact algorithms for motif discovery as the basic goal, we identify motifs based on pattern-driven, and guarantee good time performance by reducing candidate motifs and accelerating motif verification. At first, we establish the method for selecting reference sequences from large datasets, such that the selected reference sequences correspond to the minimum number of candidate motifs in all possible reference sequences. Secondly, we establish the method for generating candidate motifs from three substrings, which needs little storage space and further reduces candidate motifs. Finally, we design the efficient algorithm for motif verification, achieving the time performance of O(nl/log(n)) for verifying a candidate motif of length l in a sequence of length n. The exact algorithms designed by this project will identify motifs efficiently in large biological sequence datasets that contain hundreds or more sequences.

模体发现对生物序列中定位有意义的序列片断起着非常重要的作用。模体发现的精确算法能在指定测度下找出输入序列中最优的模体，但近年来生物序列大数据集为精确算法在时间性能方面提出了新的挑战。本项目采用基于模式驱动的技术路线进行模体发现，以设计时间高效的模体发现的精确算法为基本目标，并分别从减少候选模体和加速候选模体验证两个角度确保算法具有高效的时间性能。首先，建立在大的序列数据集中选择参考序列的方法，使选出的参考序列在所有可能的参考序列中对应最小数量的候选模体；其次，建立占用存储空间小的由三个子串生成候选模体的方法，使得进一步减小候选模体的数量；最后，设计时间高效的模体验证算法，使在长度为n的序列上验证长度为l的候选模体的时间性能达到O(nl/log(n))。本项目所设计的精确算法将能够在含有数百条甚至更多序列的生物序列大数据集中快速地进行模体发现。

(1) 项目的背景.模体发现对生物序列中定位有意义的序列片断起着非常重要的作用，但近年来生物序列大数据集为模体发现带来了巨大的计算挑战。设计适用于生物序列大数据集的时间高效的模体发现算法是当前模体发现领域的一个重要任务，有助于在基因组水平探索基因的表达调控机制。.(2) 主要研究内容.针对生物序列大数据集下的模体发现问题，本项目围绕精确的模体发现算法，主要展开了如下研究：选择恰当的参考序列对已有精确算法进行加速；设计已有精确算法适配大数据集的版本；设计高效的基于模式驱动的大数据集精确算法；设计大数据集模体发现的样本序列选择算法；研究已识别模体的时空交互关系。.(3) 重要结果.建立了模式驱动的模体识别算法的参考序列选择问题，提出了一个称为RefSelect的算法来快速地选取生成少的候选模体的参考序列，可以使现有精确算法的时间性能提升多达100倍。通过提取和合并序列中的相似子串，提出了精确算法PairMotif的适配大数据集的版本PairMotifChIP。充分分析了模式驱动的模体发现算法的计算复杂度，并设计了适用于DNA序列大数据集的模式驱动的精确算法PTMotif，时间性能显著地优胜于当前最好的精确算法。建立了模体发现的样本序列选择问题，并设计了样本序列选择算法，使得现有精确算法运行于选出的样本序列时使用很短的时间便能成功地找出模体。.(4) 关键数据及科学意义.我们在本领域重要期刊BMC Bioinformatics等和重要会议IEEE International Conference on Bioinformatics and Biomedicine (CCF B类会议)等发表了8篇论文，其中6篇为期刊论文，2篇为会议论文，SCI检索5篇，EI检索3篇。开发了可在GitHub或Google上访问的软件。这些研究成果为进一步研究具有复杂结构的模体的识别以及超大规模序列数据集上模体的搜索与识别奠定了较好的基础。