基于反转和删除操作的基因组重组全解空间研究

摘要

比较基因组学是生物信息学的一个重要分支，计算两个基因组之间的量化距离是比较基因组学的基本问题，常应用于构建物种进化树、探索基因功能、分析疾病致病原理等实践中。基因组是一组染色体的集合，染色体是细胞内具有遗传性质的的物体，可以视为一个基因序列。在有向基因组中，每个基因用一个带“+”或“-”的整数表示，符号用于表示基因的方向。
　　 基因组的重组揭示了基因组改变基因排列次序的行为，在基因组重组排序问题中表述为改变基因排列次序的操作，有反转(reversal)、移位(translocation)、转位(transposation)、反转位(tranreversal)、插入(insertion)、删除(deletion)、染色体分段(fission)、染色体连接(fussion)等基本形式。
　　 我们将包含多种操作形式的基因组重组排序称为基因组的复合重组排序问题，复合重组排序问题由于更具有一般性，因而显得更有应用价值。反转操作已经被广泛承认是基因组操作中一种最普遍的操作，科学研究发现在基因组的重组演化中，还伴有插入和删除基因片段的事件，许多分子生物学实践需要人们在基因组中实施插入和删除基因片段的操作。
　　 本文首先讨论了仅基于反转操作的基因组重组全解问题，并介绍了Braga的算法框架。然后，本文对原有的经典基因组模型进行扩展，在原有数学模型的基础上增加待删除基因块用于包含临时基因。待删除基因块可以随着反转而在基因排列的不同位置出现，我们在待删除基因块每个可能出现的位置都留下一个副本，并有一个反转操作构成的路径与之对应，用于表示该副本出现在此位置所经历的反转。本文以最少重组操作为目标，将删除操作引入到基因组重组全解问题中来，并给出了一种在最少反转距离的前提下，计算基于反转和删除两种操作的基因组全解空间的算法。最后，用Java实现了该算法，并对实验结果进行了分析。

目录

声明

摘要

第1章 绪论

1．1 应用背景

1．2 研究现状

1．3 本文的组织

第2章 基础知识

2．1 基因组定义

2．2 基因组重组操作

2．3 断点图

2．4 本文研究的具体问题

第3章 基于反转操作的基因组重组全解问题

3．1 预备知识

3．2 基于反转操作的全解空间算法

3．2．1 枚举最优i-序列算法

3．2．2 枚举全部trace的算法

第4章 基于反转和删除操作的全解空间问题

4．1 预备知识

4．1．1 问题描述

4．1．2 基本概念

4．2 模型扩展

4．3 算法描述

4．3．1 构建反转前后顺序关系

4．3．2 待删除基因块的性质

4．3．3 副本连同反转执行反转操作的算法

4．3．4 副本聚集算法

4．3．5 副本传递算法

4．3．6 整体算法框架

4．4 程序设计

4．5 实验结果

第5章 总结与展望

参考文献

致谢

攻读硕士期间发表的学术论文目录

附录

学位论文评阅及答辩情况表