论文部分内容阅读
生物信息学是将计算机领域内的知识和技术应用于研究DNA(脱氧核糖核酸)、蛋白质等生物学问题的一个迅速发展的学科领域,而生物序列比较和模式发现是生物信息学的传统课题,在系统进化、基因调控、疾病治疗、病毒起源等重要领域的研究中处于核心地位。 近年来,随着生物测序技术的突飞猛进,生物序列数据以前所未有的速度增长。人工分析和处理生物序列数据无法再满足需求,计算机和网络技术的飞速发展,为分析和处理生物序列提供了新的强大手段。本文围绕生物序列信息比较与模体(motif)发现算法问题展开研究,完成以下工作: (1) DNA序列模体发现算法研究 DNA序列是最常见的生物序列数据,在DNA序列集合中发现模体的常见方法有统计学习方法和组合优化方法。本文围绕目前最常用的FM(Fixed number of Mutation)模体发现模型展开研究,首先给出一种基于样本序列比较来组合生成候选模体的方法,然后在此基础上设计出一种新的基于样本驱动的精确算法,与现有的模式驱动算法相比,在保持精度不变的情况下降低了搜索空间,同时克服了样本驱动算法适用面窄的问题。实验表明,该算法相对目前最优的MITRA(Mismatched Tree Algorithms)精确算法的性能有了较大的提高。 (2) 纳米计算平台的生物序列处理研究 对生物序列进行比较和在生物序列中发现模体往往涉及大计算量,因此并行化的设计是必不可少的,但是问题本身的串行处理特性使得并行处理较为困难。目前已提出的一种新的纳米计算平台上的系统结构模型——Cell Matrix能较好的解决序列处理问题,其同构的二维结构便于生产和扩展,用该结构来实现序列处理算法非常自然。本文实现了可以输出比对结果的双序列比对算法,它克服了Cell Matrix模型上已有的双序列比对算法只能输出比对得分的缺陷;首次在Cell Matrix模型上设计实现了生物序列模体发现算法。并用品格数量和晶格延迟两个参数分析了两个算法的时空开销。 (3) 基因组序列的翻转排序并行算法研究 基因组序列在遗传过程中最常见变异现象为部分子序列翻转。通过对翻转排序问题串行算法的研究,在PRAM模型和LARPBS模型上分别设计出时间复杂度为O(lg~2n)和O(lgn)的并行计算有向符号序列翻转距离算法(n为序列的长度);同时在LARPBS模型上设计出一个线性时间并行翻转排序算法。