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

摘要

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

目录

文摘

英文文摘

第一章绪论

第二章单个基因组序列的重排列问题

第三章多染色体基因组之间的syntenic距离问题

第四章染色体DNA序列重组合问题

第五章广义链型结构类的序列重组合问题

第六章决定生物性状的基因组群试问题

后记

参考文献

致谢

在学期间完成的论文