| 摘要 | 第9-11页 |
| ABSTRACT | 第11-13页 |
| 第1章 绪论 | 第14-21页 |
| 1.1 算法与计算复杂性 | 第14-15页 |
| 1.2 近似算法及其性能评估 | 第15-17页 |
| 1.3 基因组序列拼接与比对 | 第17-18页 |
| 1.3.1 基因组序列拼接 | 第17页 |
| 1.3.2 序列比对 | 第17-18页 |
| 1.4 本文研究的问题及主要贡献 | 第18-21页 |
| 1.4.1 求解断点图的2-圈分解的线性时间算法 | 第18-19页 |
| 1.4.2 无向基因组移位排序问题的1.375近似算法 | 第19-20页 |
| 1.4.3 大型基因组中重复片段的检测与分析算法 | 第20-21页 |
| 第2章 求解断点图的2-圈分解的线性时间算法 | 第21-37页 |
| 2.1 引言 | 第21-22页 |
| 2.2 问题介绍 | 第22-23页 |
| 2.2.1 断点图 | 第22页 |
| 2.2.2 圈和圈分解的定义 | 第22-23页 |
| 2.2.3 断点图的2-圈分解问题定义 | 第23页 |
| 2.3 线性时间算法设计 | 第23-34页 |
| 2.3.1 简化断点图 | 第24-26页 |
| 2.3.2 断点图到匹配图的转换 | 第26-29页 |
| 2.3.3 线性时间算法 | 第29-34页 |
| 2.4 算法的时间复杂度 | 第34-35页 |
| 2.5 小结 | 第35-37页 |
| 第3章 无向基因组移位排序的1.375近似算法 | 第37-73页 |
| 3.1 引言 | 第37-38页 |
| 3.2 移位排序问题简介 | 第38-45页 |
| 3.2.1 基本概念和定义 | 第38-40页 |
| 3.2.2 有向基因组移位排序问题 | 第40-42页 |
| 3.2.3 无向基因组移位排序问题 | 第42-45页 |
| 3.3 达到1.375近似度的充分条件 | 第45-59页 |
| 3.4 1.375近似算法 | 第59-72页 |
| 3.4.1 一个基本算法 | 第59-61页 |
| 3.4.2 求解CSP诱导子图的圈分解 | 第61-67页 |
| 3.4.3 将无向基因组的断点图分解成CSP诱导子图 | 第67-69页 |
| 3.4.4 求解CSP诱导子图的补图的圈分解 | 第69-70页 |
| 3.4.5 求解整个基因组断点图的圈分解 | 第70-72页 |
| 3.5 小结 | 第72-73页 |
| 第4章 大型基因组中重复片段的检测与分析算法 | 第73-105页 |
| 4.1 引言 | 第73-74页 |
| 4.2 重复片段检测算法与断点图构造 | 第74-91页 |
| 4.2.1 检测基因组中的重复片段 | 第75-81页 |
| 4.2.2 基因组重复片段的断点图构造 | 第81-89页 |
| 4.2.3 重复片段的断点图结构分析 | 第89-91页 |
| 4.3 实验结果分析与比较 | 第91-101页 |
| 4.3.1 人类基因组中的重复片段分析 | 第91-95页 |
| 4.3.2 猿类基因组中的重复片段分析 | 第95-98页 |
| 4.3.3 老鼠基因组中的重复片段分析 | 第98-101页 |
| 4.4 总结与讨论 | 第101-103页 |
| 4.5 开放SDquest软件和相关实验结果 | 第103-105页 |
| 第5章 总结与展望 | 第105-107页 |
| 5.1 本文总结 | 第105-106页 |
| 5.2 研究展望 | 第106-107页 |
| 参考文献 | 第107-114页 |
| 致谢 | 第114-115页 |
| 攻读学位期间发表的学术论文 | 第115-116页 |
| 在读期间参与科研项目情况 | 第116-117页 |
| 外文论文 | 第117-167页 |
| 附件 | 第167页 |