论文部分内容阅读
生物信息领域中,批量蛋白质同源性搜索和模体识别是当今的两个研究热点。本文针对批量蛋白质同源性搜索问题和模体识别问题,提出了基于聚类和压缩的批量蛋白质同源性搜索算法与基于随机投影和粒子群优化的模体识别算法。通过一组蛋白质查询序列集对大规模蛋白质数据库进行同源性搜索是现代生物信息学的基本任务。过去几年里,由于高速发展的测序技术导致海量的蛋白质序列数据产生,因此,如何在大规模数据库中高效地进行批量同源性搜索已成为一个广泛关注的问题。针对这个问题,基本方法主要是对查询集中的每条序列运行BLASTP,或通过将查询集中的序列组成串联的虚拟序列之后再进行查询。然而这些方法没有考虑查询序列间或搜索数据库序列间存在的冗余性,同源性搜索的效率仍可进一步提高。基于此,本文提出了一种基于压缩和聚类的批量快速同源性搜索算法C2-BLASTP (Compression and Cluster BLASTP),本算法充分利用了数据库序列和查询序列中的冗余信息。首先,对查询序列和蛋白质数据库通过冗余分析和冗余移除过程进行压缩操作;进而对压缩后的数据库进行相似子序列聚类;然后在聚类数据库上利用映射原理进行一个粗略的查找以发现潜在结果,根据找到的潜在结果集建立可执行数据库;最后用压缩处理后的查询序列集在创建好的可执行数据库上进行同源性搜索。本文在NCBI NR数据库上进行了实验验证,并从精度、速度和内存消耗三方面验证了本算法的有效性。在基因表达和基因调控中,通过转录过程可以实现将DNA的遗传信息传递给蛋白质。转录过程中转录因子结合位点的识别可以帮助生物学研究人员了解序列之间的进化关系。识别转录因子结合位点的问题,即模体识别问题对了解序列的生物意义具有重大意义。粒子群算法中通过整合局部最优解和全局最优解来处理该问题,但存在当序列集中存在较多噪音子序列时易陷入局部最优解的问题。针对这个问题,本文提出了PSORPS (Particle Swarm Optimization Random Projection Strategy)算法。首先利用随机投影的策略过滤部分噪音序列子片段;其次,在过滤部分噪音序列子片段过程中,PSORPS可以得到分布在尽量多序列的序列片段,并将其用作粒子群群体的初始化;最后,利用重匹配和联合移动操作优化PSO求出的结果以克服碱基偏移的问题。本文在真实的生物数据集上构建实验,验证了PSORPS的有效性。