(1,2)-范例断点距离的动态规划算法研究

摘要

基因组重组问题是近20多年来计算生物学领域的研究热点，该问题在生物演化树重建、生物医药技术和发掘生物之间的亲缘关系等方面有重要的应用价值。重组排序计算结果直接用于度量两种生命的特征差异，推导两者的演化关系。快速有效的基因组重组计算方法已经成为分子生物学和医学研究与实践中探索生命演化规律的重要工具。
　　本文研究的主要内容是(1,2)-范例断点距离问题。在对范例断点距离问题的研究中，D.Bryant证明(1,2)-范例断点距离问题是NP-hard。除非P=NP，(1,2)-范例断点距离问题没有多项式时间算法。在一个基因组中，Z.Wei和D.Zhu已经得出两个相同的基因家族出现的位置经常是很小的物理距离。在此基础上，Z.Wei和D. Zhu第一次提出解决无向(1,2)-范例断点距离问题的固定参数动态规划算法。其后，Z.Wei和D. Zhu通过详细分析得出该算法的时间复杂度和空间复杂度分别为O(s4sn2)和O(s4sn)。
　　本文通过引入全局变量Map数组避免重复计算基因家族的邻接关系，将Z.Wei和D.Zhu的算法时间复杂度改进为O(s24sn)，空间复杂度保持O(s4sn)不变；当给定基因组是有向时，通过适当的修正和扩展，本文证明Z.Wei和D.Zhu的固定参数动态规划算法适合求解有向(1,2)-范例断点距离；结合Map数组，该算法能在O(s24sn)时间内实现；通过引入邻接表将无向和有向固定参数动态规划算法的空间复杂度从O(s4sn)降至O(4sn)。相关算法已经使用C++来实现，仿真对比实验进一步验证了改进算法的高效性。

目录

声明

第1章 绪 论

1.1选题背景与研究意义

1.2国内外相关文献综述

1.3主要工作和组织结构

第2章 无向EBD(1, 2)的动态规划算法研究与改进

2.1无向EBD(1, 2)的问题定义

2.2无向EBD(1, 2)的固定参数动态规划算法

2.3算法UnsignedExemplar(G1, G2)描述

2.4无向(1, 2)-范例断点距离动态规划算法仿真对比实验

2.5本章小结

第3章 Li有向EBD(1, 2)动态规划算法的研究与改进

3.1有向EBD(1, 2)的问题定义

3.2修订动态规划算法解决有向EBD(1,2) 问题

3.3算法SignedExemplar(G1, G2)描述

3.4有向(1, 2)-范例断点距离动态规划算法仿真对比实验

3.5本章小结

第4章 使用邻接表实现改进的EBD(1,2)动态规划算法

4.1邻接表实现EBD(1, 2)算法降低算法空间复杂度

4.2使用邻接表实现改进的无向EBD(1,2)动态规划算法

4.3使用邻接表实现改进的有向EBD(1, 2)动态规划算法

4.4无向和有向EBD(1,2)的动态规划算法实验结果比较

4.5本章小节

第5章 总结与展望

5.1总结

5.2展望

参考文献

致谢

附录A 攻读学位期间所发表的学术论文目录