论文部分内容阅读
模体发现在系统进化、基因调控等领域处于核心地位。模体中蕴含丰富的生命遗传信息,由于其长度,位置,变异的不确定性,模体发现问题仍然是一个难点。本文分析了聚类应用在模体发现问题上的可行性,提出了基于马尔可夫(MCL)聚类求解该问题的算法。应用滑窗机制和降维策略,缩小原始数据至MCL算法可处理的规模大小。通过MCL聚类把相似度高的l-mer自适应的聚集在同一个子类中。对聚类产生的子类进行“去杂”——提取子类内部蕴含的最大团,对所有的子类施加一种基于启发式的遗传算法,找出每个子类的最大团,作为算法挖掘的候选模体实例集。在候选模体实例集上,应用相对熵作为测度进行评判,择优输出,发现最终的模体实例。本文使用了模拟数据和实际生物数据对算法进行了聚类产生的子类自身的特性和子类之间相关性分析。对每个子类中蕴含的不同最大团进行了分析,找出了同一子类中最大团之间的互补和重叠关系,以及这些关系和算法nPC性能的关系。通过相对熵测度的分析,比对了Top1和TopK原则对算法的影响。测量性能系数nPC和nCC,验证了算法的有效性。对模拟生物数据和保守性较强的真实生物数据取得的性能都比较满意,并和MEME算法进行效果比较。