| 摘要 | 第1-17页 |
| ABSTRACT | 第17-22页 |
| 第1章 绪论 | 第22-35页 |
| ·算法与计算复杂性 | 第22-23页 |
| ·近似算法、近似性能比及不可近似性 | 第23-26页 |
| ·L-归约与APX-hard | 第25-26页 |
| ·参数化算法与核心化 | 第26-27页 |
| ·搜索问题与亚核 | 第27-29页 |
| ·本文研究的问题及主要贡献 | 第29-34页 |
| ·无符号多染色体线性基因组DCJ距离问题的亚核和近似算法 | 第30页 |
| ·排列短块移动排序问题的近似算法 | 第30-31页 |
| ·字串最小公共子串划分问题的复杂性和参数化算法 | 第31-32页 |
| ·基因组最长带恢复问题及其补问题的亚核及算法 | 第32页 |
| ·基因组片段填充问题的复杂性和近似算法 | 第32-33页 |
| ·PQ-树断点距离相似性比较问题的复杂性和参数化算法 | 第33-34页 |
| ·最大路径覆盖补问题的亚核和参数化算法 | 第34页 |
| ·参考文献 | 第34-35页 |
| 第2章 基因组二次切割与连接排序问题的算法设计 | 第35-47页 |
| ·引言 | 第35-36页 |
| ·问题介绍 | 第36-38页 |
| ·基因,染色体和基因组 | 第36页 |
| ·断点图(Breakpoint Graph) | 第36-37页 |
| ·二次切割与连接操作(Double Cut and Join) | 第37-38页 |
| ·近似算法设计 | 第38-44页 |
| ·无向基因组二次切割与连接排序的性质 | 第38-41页 |
| ·算法形式化描述 | 第41-44页 |
| ·核与参数化算法 | 第44-45页 |
| ·结论 | 第45-46页 |
| ·参考文献 | 第46-47页 |
| 第3章 基因组排列的短块移动排序问题 | 第47-88页 |
| ·引言 | 第47-48页 |
| ·短块移动问题简介 | 第48-49页 |
| ·Heath的结论及算法 | 第49-51页 |
| ·改进算法 | 第51-64页 |
| ·伞排序 | 第51-57页 |
| ·(1+ε)-近似算法 | 第57-58页 |
| ·关联伞排序 | 第58-62页 |
| ·短块移动排序近似算法 | 第62-64页 |
| ·算法的近似性能比分析 | 第64-86页 |
| ·特殊排列短块移动距离下界 | 第64-75页 |
| ·算法近似性能比分析 | 第75-86页 |
| ·结论 | 第86页 |
| ·参考文献 | 第86-88页 |
| 第4章 最小公共划分问题 | 第88-97页 |
| ·引言 | 第88-90页 |
| ·问题介绍 | 第88-89页 |
| ·相关工作 | 第89页 |
| ·本文贡献 | 第89-90页 |
| ·MCSP~c的复杂性 | 第90-92页 |
| ·d-MCSP的FPT算法 | 第92-94页 |
| ·x-balance MCSP的FPT算法 | 第94-95页 |
| ·总结 | 第95页 |
| ·参考文献 | 第95-97页 |
| 第5章 基因组最长带恢复问题的亚核与算法 | 第97-113页 |
| ·引言 | 第97-98页 |
| ·问题介绍 | 第98-99页 |
| ·参数化算法和亚核 | 第98-99页 |
| ·线性亚核 | 第99-104页 |
| ·3~k参数化算法 | 第104-107页 |
| ·3-近似算法 | 第107-111页 |
| ·算法描述 | 第107-108页 |
| ·近似性能比证明 | 第108-111页 |
| ·结论 | 第111-112页 |
| ·参考文献 | 第112-113页 |
| 第6章 基因组片段填充问题的算法与复杂性 | 第113-129页 |
| ·引言 | 第113-114页 |
| ·本文贡献 | 第113-114页 |
| ·问题介绍 | 第114-116页 |
| ·多项式时间算法 | 第116-121页 |
| ·双面排列断点距离填充问题的多项式算法 | 第116-118页 |
| ·双面排列断点二次切割与连接距离填充问题的多项式算法 | 第118-121页 |
| ·复杂性证明 | 第121-125页 |
| ·最小公共划分片段填充问题是NP-Complete的 | 第121-123页 |
| ·最大公共邻接片段填充问题是NP-Complete的 | 第123-125页 |
| ·最大公共邻接片段填充问题的近似算法 | 第125-127页 |
| ·简单的2-近似算法 | 第125-126页 |
| ·单面最大公共邻接片段填充问题的4/3-近似算法 | 第126-127页 |
| ·结论 | 第127-128页 |
| ·参考文献 | 第128-129页 |
| 第7章 PQ-树相似性比较问题复杂性与算法 | 第129-139页 |
| ·动机 | 第129页 |
| ·引言 | 第129-131页 |
| ·排列、断点及中心 | 第129-130页 |
| ·PQ-树 | 第130页 |
| ·问题描述 | 第130-131页 |
| ·有结果及本文贡献 | 第131页 |
| ·PQ-树断点距离问题是NP-Complete的 | 第131-135页 |
| ·单面MBP-PQ和p-MBM-PQ的参数化算法 | 第135-137页 |
| ·PQ-树的图表示 | 第135页 |
| ·单面MBP-PQ问题的FPT算法 | 第135-137页 |
| ·参数化算法应用于p-MBM-PQ | 第137页 |
| ·结论 | 第137页 |
| ·参考文献 | 第137-139页 |
| 第8章 最大路径集覆盖问题的亚核与参数化算法 | 第139-145页 |
| ·引言 | 第139-140页 |
| ·动机 | 第139页 |
| ·研究状况 | 第139页 |
| ·本文工作 | 第139-140页 |
| ·问题介绍 | 第140页 |
| ·5k亚核 | 第140-142页 |
| ·改进参数化算法 | 第142-144页 |
| ·结论 | 第144页 |
| ·参考文献 | 第144-145页 |
| 第9章 总结与展望 | 第145-147页 |
| ·本文总结 | 第145-146页 |
| ·研究展望 | 第146-147页 |
| 致谢 | 第147-148页 |
| 攻读学位期间发表的学术论文 | 第148-149页 |
| 在读期间参与科研项目情况 | 第149-150页 |
| 学位论文评阅及答辩情况表 | 第150-152页 |
| 外文论文 | 第152-184页 |
