生物信息学是一门融合了了计算机、数学、物理等各个领域知识的新兴的、非常重要的交叉学科。生物信息学在近十几年的飞速发展极大地推动了生物学的研究,同时也给其它相关领域提供了一系列富有挑战性的的问题。本文主要研究的问题是如何利用组合算法来研究和预测原核生物中的调节子。转录既是DNA翻译成蛋白质的关键一步,同时也是调控基因表达的关键阶段。原核生物中的基本转录单元是操纵子,被同一个转录因子调控的操纵子的集合称为调节子。我们要想搞清楚原核生物细胞中的整体转录调控机制,就十分有必要对调节子进行深入的研究。一个调节子只有在特定的实验条件下才能在实验中被发现,通过遍历实验条件的方法来确定调节子是不现实的。因此在本文中我们提出了一个基于组合优化的计算方法,力求透彻的研究并完整的预测原核生物中的调节子。这个算法的成功执行要依赖于以下的三个方面的准备工作：第一,调控模体的准确预测；第二,分析基因表达数据的双聚类方法；第三,物种间直系同源基因的准确预测。这三个方面的进展都会从根本上推动调节子的研究。在这篇论文中,我们首先介绍了一个全新的模体预测软件：BOBRO。它可以对任意给定的启动子序列集合来预测转录调控模体,极大地改进了模体预测问题的整体性能并且扩展了软件的应用范围。其改进主要体现于如下两个方面：(1)设计了一个全新高效的模体信号挖掘组合算法,能够大大的加强相似模体之间的相互支持,并且运用寻找极大团的算法来构建初始的种子模体集合。(2)从种子集合出发,我们利用模体闭包的概念,扩展种子、优化模体集合并评价最终模体集合。在一系列大肠杆菌K12共调控数据上,我们比较了BOBRO和其他五个常用的模体预测软件的预测结果,实验结果证明与其他所有软件相比,BOBRO至少提高了42%的模体预测准确率。另一组实验结果表明,BOBRO在整个大肠杆菌K12基因组上成功预测了1472个已经通过生物实验证实了的转录调控模体,为最终调节子的确定打下了坚实的基础。然后我们给出了一种基于组合优化算法的基因表达数据的双聚类分析软件：QUBIC。这个软件相对于目前已有的双聚类方法,能够在更加一般的情况下解决双聚类的问题。主要特征有：(1)能够准确的确定出所有具有统计意义的双聚类,也包含公认不好确定的缩放型的双聚类；(2)能够十分高效的处理大规模的基因表达数据。分析一个行和列都数以千计的基因表达矩阵只需要短短的几分钟时间。通过在人工模拟数据和真实的生物数据上的实验结果,我们看到了QUBIC相对于其它软件在双聚类的分析性能上有了大幅度的提高。最后一个准备工作就是原核生物中同源基因的确定。我们对这个问题同样提出了一个组合算法：GOST,它相对于这个领域的其它方法的特点是：(1)在算法中整合了操纵子在进化过程中的保守性；(2)在两个基因组之间运用了一个整体最优的准则来确定直系同源关系。GOST相对于我们选取的目前比较流行的三个软件,在预测结果的覆盖度和错误率两个方面都有很大程度的改进。进一步的我们关注GOST的预测结果与其他软件预测结果中不一致的直系同源关系,其中77%可以利用另外的三种生物相关的验证方法进行验证。值得一提的是我们的方法使用方便且十分高效,在两个全基因组之间确定所有的同源关系大约只需要10分钟的时间。在调控模体和同源基因的准确预测的基础上,我们给出了一个预测调节子的组合算法：REGUP,试图确定一个原核生物基因组中编码的所有调节子。据我们所知,目前还没有任何一个软件能够在全基因组上大规模的预测调节子。进一步的我们利用大肠杆菌K12中已知的178个调节子和466个实验条件下的基因表达数据对算法进行了验证和调整。另外,文中所有提到的软件都会随着我们工作的进展逐渐的公布出来。