《有向基因组复合操作重组排序算法研究》由会员分享，可在线阅读，更多相关《有向基因组复合操作重组排序算法研究（152页珍藏版）》请在金锄头文库上搜索。
1、r 分类号：T P 3 0 10 7 8 4 密 级： 单位代码： 学号： 1 0 4 2 2 2 0 0 7 2 0 4 7 5 菇办孑 博士学位论文 S h a ，7d o n gU n i v er s i t yD0Ct0raI Di88erta ti0n 论文题目：有向基因组复合操作重组排序算法研究 A l g o r i t h m sf o rS o r t i n gS i g n e dG e n o m e sb y M u l t i p l e - - O p e r a t i o nR e a r r a n g e m e n t s 郝凡昌 计算机软件与理论 朱
2、大铭教授 2 0 11 年4 月2 0 日 ktt，一I r 者 业 师 作 专 导 、 J 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：蔫峰轧 日 论文作者签名：飞晖盟江 日 期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件
3、和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 做储签名摊新躲槛日 期：型型 - 弦 I 山东大学博士学位论文 目录 摘要I A B S T R A C T I V 符号说明V I I I 第l 章绪论1 1 1 有向基因组排序算法进展2 1 2本文的主要贡献6 第2 章有向基因组排序问题介绍8 2 1基因组的表示方法8 2 2基因组排序问题模型9 2 2 1 重组操作9 2 2 2 对输入基因组的约束1 2 2 3 问题定义及输出一1
4、3 2 4研究工具圈图。1 3 2 5本文研究的具体问题。1 4 第3 章基因组的移位和删除排序问题。1 6 3 1 问题介绍1 6 3 1 1 问题描述1 6 3 1 2 预备知识1 6 3 2问题分析2 0 3 3 已有的算法。2 2 3 4 基因组的移位和删除排序精确算法2 7 3 4 1 对所有情况的分析2 7 山东大学博士学位论文 3 4 2 基因组的移位和删除距离公式3 0 3 4 3 算法性能分析4 l 3 5 结论4 6 第4 章基因组的移位和删除排序问题扩展。4 7 4 1基因组的移位和删除排序问题的较快算法。4 7 4 1 1 基因组的移位和删除排序问题的较快算法4 7 4
5、 1 2 较快算法分析5 0 4 2 相关操作的可逆性5 3 4 3基因组的移位和插入排序问题5 3 4 3 1 问题描述：5 3 4 3 2 归约为“基因组的移位和删除排序问题”。5 4 4 4 基因组的移位、插入和删除排序问题5 4 4 4 1 问题描述5 5 4 4 2 算法及分析。5 5 4 5结论。6 0 第5 章一般基因组的复合操作排序问题6 l 5 1问题描述6 l 5 2启发式方案的架构设计6 2 5 2 1 解决该问题的三个功能模块6 3 5 2 2 解决方案的实现组件。6 5 5 3 去除多倍染色体和副本基因6 7 5 3 1 染色体丢失组件一6 7 5 3 2 副本基因标
6、识组件6 8 5 - 3 3 反任意片段复制组件一7 0 5 4同尾化基因组7 2 I I 山东大学博士学位论文 5 4 1 加帽基因组。7 2 5 4 2 各种操作在加帽前后的对应关系。7 3 5 4 3 同尾化基因组的实现组件7 4 5 5规范基因组的排序7 6 5 6 结果与分析7 8 第6 章总结与展望8 2 6 1 本文总结。8 2 6 2研究展望8 3 参考文献8 4 致谢9 5 攻读学位期间发表的学术论文目录。9 6 在读期间参与科研项目情况9 7 学位论文评阅及答辩情况表。9 9 外文论文1 0 1 I I I 山东大学博士学位论文 T A B L Eo FC o N T E
7、N T S A B s t r a c ti nC h i n e s e I A b s t r a c ti nE n g l i s h I V N o t a t i o n a lD e s c r i p t i o n s V I I I C h a p t e r1I n t r o d u c t i o n 1 1 1S u m m a r i z eo f A l g o r i t h m sf o rS o r t i n gS i g n e dG e n o m e s 2 1 2M a i nC o n t r i b u t i o n s 6 C h a p
8、 t e r2I n t r o d u c t i o nt oS o r t i n gG e n o m eP r o b l e m s 8 2 1T h eE x p r e s s i o no f G e n o m e s 8 2 2P r o b l e mF o r m u l a t i o n 9 2 2 1 R e a r r a n g e m e n tO p e r a t i o n s 9 2 2 2R e s t r a i n t st oG e n o m e s 1 2 2 3 D e f i n i t i o no fT h eP r o b l
9、 e m 13 2 4 C y c l eG r a g l l 1 3 2 5P r o b l e m sS t u d i e di nt h i st h e s i s 14 C h a p t3S o r t i n gG e n o m e sb yT r a n s l o c a t i o n sa n dD e l e t i o n s ( S O T D ) 16 3 1I n t r o d u c t i o n 1 6 3 1 1P r o b l e mF o r m u l a t i o n 1 6 3 1 2P r e l i m i n a r i e s 16 3 2P r o b l e m A n a l y s i s 2 0 3 3P r e v i o u sA l g o r i t h m 2 2 3 4 A nA c c u r a t eA l g o r i t h r nf o rS G T D 2 7 3 4 1 A n a l y s i so f A l lT h eC a s e s 2 7 3 4
