论文部分内容阅读
在一组生物序列中,通常会存在一些含有特定功能的短的序列片段,比如DNA序列中的转录因子结合位点。这些序列片段之间比较相似,但并不相同,这样的序列片段被统称为模体。研究者们一般采用计算的手段,识别生物序列中的模体。这类求解问题就是模体发现问题。在生物信息学和计算机科学中,模体发现问题都是重要且挑战性的问题。植入(l,d)模体发现(PMS)问题是模体发现的一种常用的研究形式,自被Keich和Pevzner第一次提出至今,已涌现出来了许多用于求解植入(l,d)模体发现问题的算法。本文主要关注于其中的精确算法,它们通过遍历整个搜索空间能够找出所有的模体,时间性能是衡量精确算法的最主要指标。研究者一般在模体发现问题的挑战实例上比较不同精确算法的时间性能。在目前对精确算法的研究中,基于模式驱动的精确算法具有最好的时间性能,无论是识别短模体还是微弱信号的长模体。这类精确算法的基本思路是用t条输入序列中的k(1≤k<t)条作为参考序列来生成候选模体,再逐一对候选模体进行验证,可以找出输入序列中所有的(l,d)模体。然而,在选择序列中的参考序列时,基于模式驱动的精确算法大多数都是固定地将输入序列中的前k条作为参考序列,没有考虑不同的参考序列对算法时间性能的影响。我们在本文的研究中发现,对于同一组数据集,不同的参考序列对候选模体的数量存在着影响,特别是对于大的字符集。因此在实验中,基于模式驱动的精确算法在应对同等规模的不同输入时,时间性能有时会表现出极大的不稳定性。在本文中,我们建立了模体发现算法中的参考序列选择问题,并通过评估不同参考序列对应的候选模体数量,提供了一种为模式驱动的模体发现算法选择参考序列的方法RefSelect,使得选出的参考序列对应于少的候选模体。实验结果表明,RefSelect算法(1)使得qPMS7算法、TraverStrR算法和PMS8算法等能够稳定地以高效的方式求解模体发现问题;(2)特别地,在蛋白质数据集上,对这些算法有数百倍的加速;(3)同时,在序列数量较多的大数据集上,RefSelect算法同样适用。