转录因子结合位点是一段短的DNA序列,长度一般在10bp～30bp之间,它通常位于被调控基因上游的启动子区域中,转录调控蛋白与这些序列结合才能对基因的转录进行调控。因此识别转录因子结合位点成为构建转录调控网络的第一步。通常一种转录调控蛋白具有多个结合位点,这些位点在序列模式上具有相似性但又不完全相同,因此寻找一个转录调控蛋白的全部结合位点成为当今生物信息学领域最具挑战性的问题之一。本文提出一种利用图论知识对与一个转录调控蛋白结合的所有已知转录因子结合位点进行聚类从而识别未知转录因子结合位点的方法。通过对已知的转录因子结合位点进行聚类,我们可以把相似性最高的序列分到一组,对每一组中的序列构建位置特异性得分矩阵,从而得到多个位置特异性得分矩阵,把这些位置特异性得分矩阵组合在一起就形成所有已知的转录因子结合位点的混合位置特异性得分矩阵模型。我们用这个模型对训练集中的序列进行打分从而形成得分向量,用这些得分向量训练一个分类器,训练好的分类器就具有识别这种转录调控蛋白的结合位点的能力。理论上,我们的聚类方法不需要预先确定聚类数目而是根据序列之间的相似性自适应的调节聚类数,因此聚类效果比传统的聚类方法有较明显提高,另外,通过聚类得到的混合位置特异性得分矩阵模型的信息含量比单一的位置特异性得分矩阵高,因此用它给转录因子结合位点序列打分受随机事件的影响较小,分数更加可靠,训练分类器的效果更好,因此我们的方法比传统的方法更具优势。实验上,我们首先通过大肠杆菌转录因子结合位点测试我们的方法,结果识别效果比传统的位置特异性得分矩阵方法有明显提高。接着我们又对酵母的四个转录调控蛋白的结合位点序列进行试验,结果表明,使用我们的方法进行转录因子结合位点识别,在识别的敏感性和特异性上均比传统的位置特异性得分矩阵方法有较大提高,从而说明我们的方法在转录因子结合位点识别上是有效的。