论文部分内容阅读
复合模式查找是生物信息学中模式发现问题的一个新的研究领域，而寻求效率更高，精度更高的复合模式查找算法将是此研究领域的热点与目标。复合模式查找问题是模式查找问题的泛化形式，而复合模式查找的难点在于组成复合模式的其中一个或多个单分体模式可能“太弱”，即不具有统计显著性，因此通常用于查找单分体模式的方法很难应用于复合模式查找。本文提出一种改进的基于分步的复合模式查找算法，称为IACF算法（theImproved Algorithm for Composite Pattern Discovery based on Fractional Steps），IACF算法将随机投影算法、遗传算法和多序列比对算法结合在一起：首先使用随机投影算法和遗传算法查找复合模式中强单分体的模式实例；再在其下游或上游一定距离范围内定位出另一个弱单分体的候选模式实例，用多序列比对找到每条序列的弱的单分体的模式实例，并记录两个单分体模式实例间的距离，组合两部分得到复合模式实例；最后用不考虑空位和碱基相关性的共有序列表示法得出复合模式。IACF算法只需要查找复合模式中较强部分的单分体模式，且整个过程只需要进行一次查找。通过实验表明，IACF算法对于模拟数据和真实数据都有其实用性，与RISO、MITRA-Dyad、ECOMP算法相比，IACF算法内存占用较少，且在复合模式中存在一个较强单分体模式的情况下，查找时间少于其它三种算法。