论文摘要
用计算的方法查找基因调控子的结合位点是生物信息学的一个非常重要研究课题。在基因转录过程中,其表达在很大程度上受到一些顺式作用元件(即转录调控元件,调控子结合位点)的控制,它们本质上是一些比较短的DNA序列,这些序列一般都处在受调控基因的上游区域。特异性DNA结合蛋白(即调控子,转录因子)识别这些调控元件,并与之结合,调节DNA的代谢和转录;或者由RNA结合蛋白识别,并与之结合,影响RNA的修饰、定位、翻译和降解。因此,分析和识别调控子结合位点以及了解它们的功能是理解和解释整个基因组行为的重要步骤。本文的工作主要集中在用计算的方法查找调控子结合位点。首先回顾了经典的两个算法:EM算法和Gibbs采样方法查找结合位点。第三章给出了一个新的用进化计算的方法查找结合位点的计算框架,并在此框架下实现了遗传算法和粒子群算法,这两个最常用的进化计算方法。第四章给出了一个贪心算法,并且对此贪心算法进行了有效改进,大大降低了算法的时间复杂度。之后,将此贪心算法与遗传算法相结合,获得了更好的结果。