模体(Motif)是指一组序列中局部的保守区域,或者是一组序列中共有的一小段序列模式。更多的时候是指有可能具有与分子功能、结构性质或家族成员相关的任何序列模式,其主要存在于蛋白质、DNA、RNA等序列中。模体的发现对研究基因表达意义重大,是后基因时代生物信息学中的一个主要研究方向。目前模体发现问题研究主要集中于转录因子结合位点,即在DNA序列中具有特定功能并且保守的序列片段。而对限制性内切酶结合位点的发现问题同样是模体发现研究领域中的一个重要研究点。与前者不同,后者则是加入了一些限定条件。限制性内切酶结合位点挖掘问题是指给定正例和反例核苷酸序列集合,并指定模式P,要求找到符合模式P的模体m只在正例序列集合中有模体实例存在,而在反例序列集合中不能出现模体m的实例。在这个过程中核苷酸序列的反向互补序列也要考虑进去,因此这类问题可以看作是一种限定性的模体发现问题。此类具有限定性的模体的发现可以推断出新的限制性内切酶,进而可以针对不同外源DNA使用相应的内切酶破坏其DNA结构以限制其侵入,从而起到了保护细胞原有的遗传信息的作用。虽然目前在转录因子结合位点研究领域已经出现了很多算法和相应的软件,如MEME、AlignACE、Gibbs Sampler、PMS系列等。这些算法中,多数算法及其改进算法可以很好地解决多数模体挖掘问题,但这些算法并不能直接用于寻找带有限定性的模体发现问题。因此本文针对该类模体发现问题提出了两种有效的算法——倒排索引算法和L-PMS算法。倒排索引算法(Inverted Index Algorithm)首先以字典顺序列出给定模式P的所有实例I={I1...N},然后对每个实例Ii进行比较验证,若该实例满足只出现在正例序列集合中,而在反例序列集合中不出现的要求,则该实例作为最终模体输出;L-PMS算法基于PMS8算法,PMS8算法是植入模体发现问题(Planted Motif Search,PMS)中的一种比较高效的算法。L-PMS算法对PMS8算法进行了改进,将PMS8算法中的植入(l,d)实例问题和指定模式P问题相结合,很好地解决了限定性模体发现问题。