计算生物学中若干组合优化问题的研究

论文摘要

本文主要研究了计算分子生物学中的若干组合优化问题。全文共分为六章。在论文的第一章里,首先简要介绍了组合优化,计算生物学问题,算法和时间复杂性等基本概念。 第二章主要研究了单个基因组序列的重排列问题。我们提出一种更具有一般性意义的新移位操作,并且设计出利用逆序和这种新移位操作对单染色体基因组重排列的近似算法。 第三章主要研究多染色体中基因组重定位问题。针对多染色体基因组重定位的一类松弛问题,称作Syntenic距离问题,我们提出一个新的特殊可解情形,称为无覆盖特殊类,并且设计出了相应的多项式时间最优算法。 第四章研究了染色体DNA序列重组合问题。我们研究这类问题的多项式时间特殊可解结构。我们针对一类“树型”结构,指出解这类特殊结构的已有算法的不完备性,并且对重组“树型”结构进行了更加全面的考虑,设计出新的算法,并严格证明了新算法的最优性。在这一章中,我们还将新提出一类DNA序列的特殊可解结构——“链型”结构,设计出了最优算法,实现了向“链型”结构DNA序列重组合的最优演变过程。 在第五章里,我们重点讨论DNA序列重组合中,“链型”结构重组合问题的推广。我们将第四章中所提出的“链型”结构的限制性条件放宽了,提出了更具普遍意义下的“广义链型”结构,分若干情形讨论了重组合“广义链型”结构的最优过程,并且设计了最优算法实现这一过程。 第六章主要研究了决定生物性状的基因组群试问题。我们建立了决定生物性状的基因组群试模型,即超图上的群试问题,并且首次提出了一个求解该问题的竞争算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 组合优化简介
• 1.2 计算生物学中的组合优化问题
• 1.3 算法和计算复杂性
• 1.4 论文概述
• 第二章 单个基因组序列的重排列问题
• 2.1 引言
• 2.2 预备知识
• 2.3 操作数下界
• 2.4 一个2倍近似算法
• 第三章 多染色体基因组之间的syntenic距离问题
• 3.1 引言
• 3.2 预备知识
• 3.3 连通的无覆盖synteny特殊类
• 3.4 不连通的无覆盖synteny特殊类
• 第四章 染色体DNA序列重组合问题
• 4.1 引言
• 4.2 预备知识
• 4.3 生成树型结构类的最优算法
• 4.4 生成链型结构类的最优算法
• 第五章 广义链型结构类的序列重组合问题
• 5.1 引言
• 5.2 广义链的定义及预备知识
• 5.3 广义3-链、广义4-链的最优重组合过程
• 5.3.1 广义3-链的最优重组合过程
• 5.3.2 广义4-链的最优重组合过程
• 5.4 生成广义链的最优算法
• 5.4.1 连续m-链的最优重组合算法
• 5.4.2混合m-链的最优重组合算法
• 第六章 决定生物性状的基因组群试问题
• 6.1 引言
• 6.2 在r-图中测试的一般方法
• 6.3 在r-图中测试的一个竞争算法
• 6.4 在超图中测试的一个竞争算法
• 后记
• 参考文献
• 致谢
• 在学期间完成的论文