生物序列数据比较与模体发现算法研究

《生物序列数据比较与模体发现算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学博士学位论文生物序列数据比较与模体发现算法研究姓名：沈一飞申请学位级别：博士专业：计算机软件与理论指导教师：陈国良20060501摘要生物信息学是将计算机领域内的知识和技术应用于研究DNA(脱氧核糖核酸)、蛋白质等生物学问题的一个迅速发展的学科领域，而生物序列比较和模式发现是生物信息学的传统课题，在系统进化、基因调控、疾病治疗、病毒起源等重要领域的研究中处于核心地位。、近年来，随着生物测序技术的突飞猛进，生物序列数据以前所未有的速度增长。人工分析和处理生物序列数据无法再满足需求，计算机和网络技术的飞速发展，为分析和处理生

2、物序列提供了新的强大手段。本文围绕生物序列信息比较与模体(motif)发现算法问题展开研究，完成以下工作：(1)DNA序列模体发现算法研究DNA序列是最常见的生物序列数据，在DNA序列集合中发现模体的常见方法有统计学习方法和组合优化方法。本文围绕目前最常用的FM(FixednumberofMutation)模体发现模型展开研究，首先给出一种基于样本序列比较来组合生成候选模体的方法，然后在此基础上设计出一种新的基于样本驱动的精确算法，与现有的模式驱动算法相比，在保持精度不变的情况下降低了搜索空间，同时克服了样本驱动算法适用面窄的问题。实验

3、表明，该算法相对目前最优的MITRA(MismatchedTreeAlgorithms)精确算法的性能有了较大的提高。(2)纳米计算平台的生物序列处理研究对生物序列进行比较和在生物序列中发现模体往往涉及大计算量，因此并行化的设计是必不可少的，但是问题本身的串行处理特性使得并行处理较为困难。目前已提出的一种新的纳米计算平台上的系统结构模型——CellMatrix能较好的解决序列处理问题，其同构的二维结构便于生产和扩展，用该结构来实现序列处理算法非常自然。本文实现了可以输出比对结果的双序列比对算法，它克服了CellMatrix模型上已有的双

4、序列比对算法只能输出比对得分的缺陷；首次在CellMatrix模型上设计实现了生物序列模体发现算法。并用晶格数量和晶格延迟两个参数分析了两个算法的时空开销。(3)基因组序列的翻转排序并行算法研究基因组序列在遗传过程中最常见变异现象为部分子序列翻转。通过对翻转排序问题串行算法的研究，在PRAM模型和LARPBS模型上分别设计出时间复杂度为O(192，z)和0(19，z)的并行计算有向符号序列翻转距离算法(订为序列的长度)；同时在LARPBS模型上设计出一个线性时间并行翻转排序算法。摘受中冈科学技术人学博㈠．--“7-‘-位论义；(4)计算

5、基于翻转距离的基因组序列的中值序列(简称翻转中值)算法研究计算基因组序列的中值序列问题是用基因组信息创建生物进化树的基础。本文将有向符号序列的翻转中值问题转化为一个图论问题，在此基础上给出一个时间复杂度为O(n驯+1)精确算法，其中1l为序列的长度、d为给定序列之间的距离的线性函数：接着将此算法推广到类似的计算基因组重排的中值序列问题；通过对中值路径上排列的翻转距离研究，推导出该类排列的性质，在其基础上给出两个最坏时间复杂度均为o(i12d+I)的分支限界算法，实验表明，在大多数情况下算法具有很好的性能。本文的贡献与创新之处在于：1、设

6、计一种新的DNA序列模体发现精确算法该算法结合已有的模式驱动算法和样本驱动算法特点，并首次在算法中引入序列比较来组合生成候选模体，大大缩小了搜索空间。实验表明该算法的性能优于目前我们已知的最快精确算法。2、给出计算有向符号序列的翻转距离和翻转排序的并行算法首次采用倍增技术设计了计算有向符号序列的翻转距离的并行算法；在LARPBS模型上设计了使用O(n3)个处理器时间复杂度为D(19，z)的并行连通分量算法；在O(n!)处理器数目的LARPBS模型上设计出翻转排序并行算法，该算法将现有的翻转排序并行算法最快时间复杂度由O(nlgn)降低到

7、D(，2)。3、提出计算基于翻转操作的有向符号序列中值序列精确算法提出目前最好的精确算法，将时间复杂度O(n3‘)降为O(n2州)，其中d敛。设计了计算基于翻转操作的有向符号序列分支限界算法，其最坏情况下时间复杂度为O(n2水1)，比起直接计算方法，它极大降低了搜索空间规模，试验表明分支限界算法具有优异的性能。关键词：生物模体发现，基因组重排，翻转排序，翻转中值，并行算法，纳米计算，序列比对。ABSTRACTBeingoneoftheacadenaicareasthatdeveloprapidly,Bioinfonnaticsusesk

8、nowledgeillcomputersciencetOsolvebiologyproblenlsconcerningDNA，proteinetc．Bio．sequencecomparisouandlnot