论文题目: 计算生物学中的组合优化问题的研究
论文类型: 博士论文
论文专业: 运筹学与控制论
作者: 王骁力
导师: 李国君
关键词: 基因组重排,多重基因组,移位距离,基因组进化距离,中值问题,排序,蛋白质相似性,近似算法
文献来源: 山东大学
发表年度: 2005
论文摘要: 基因组重排的问题产生于上个世纪七十年代,主要目的是利用已知的DNA数据去确定不同物种之间的相似与差异。基因组重排在比较遗传学中提供了分子进化的一个普遍的模式,它可以对生物学及其他学科提供生物上的有益的刻划。 基因组重排问题就是寻找最少数目的进化变换把一个基因组变成另一个基因组。这个最小的进化变换数目称为对应的两个基因组之间的进化距离。我们把求从一个基因组变成另一个基因组的最短的进化变换序列问题称为基因组排序问题。此组合优化问题已成为理论计算机科学与数学领域一个基本的研究课题。 基因组重排与蛋白质相似性搜索是近几年来计算生物学中研究的难点与热点。目前有关单染色体基因组的研究比较充分和完善,而有关多染色体基因组的研究不多,并且研究成果很欠缺。本文对多染色体基因组的进化距离计算问题与基因组排序问题进行了研究,着重讨论了与基因组的进化距离有关的算法,给出了问题的最优算法与近似算法,分析了所给算法的复杂性,同时比较了新算法和已有算法,本文的算法都优于已有算法。另外,本文就蛋白质相似性搜索问题,给出了一个相关问题的近似算法和复杂性分析。全文共分七章。 第一章绪论介绍了本文考虑的计算生物学中的组合优化问题:基因组重排与蛋白质相似性搜索问题产生的理论背景,常用术语与符号,本文结构与主要内容。 第二章研究(交互的)移位变换下的有向多染色体基因组的基因组进化距离计算问题。我们称这里的进化距离为移位距离。这个问题于1996年被S.Hannenanlli证明是P问题,同时给出了复杂性为O(n~3)的多项式时间算法。此问题被朱大铭,马绍汉于2002年算法的时间复杂性改进为O(n~2logn),王路生等人于2004年把求解对应的排序与距离计算问题的算法的时间复杂性改进为O(n~2).本章考虑移位距离计算问题。 ·有向排列的圈图的结构,把求有向排列的圈交叠图连通分支的问题转化为求其边交叠图的连通分支的问题,设计出该问题的线性时间算法,即算法2-1。它在第
论文目录:
Chinese abstract
English abstract
Notation index
Chapter 1. Introduction
§1.1 Motivation: background of the research
§1.2 The mathematics model in genome rearrangements
§1.2.1 Chromosome, genome and transformation
§1.2.2 Reversals on signed permutations
§1.3 The media problem
§1.4 Protein similarities search
§1.5 Some key concepts of algorithms
§1.6 Related work and new results
Chapter 2. Translocation Distance between Signed Genomes
§2.1 Introduction
§2.2 Problem formulation and preliminary results
§2.2.1 Translocation on signed genomes
§2.2.2 Problem formulation and preliminary results
§2.3 Linear algorithm to compute the translocation distance
§2.4 Conclusion
Chapter 3. Genomic Distance Between Signed Genomes
§3.1 Introduction
§3.2 Preliminary results
§3.2.1 Transformations on uni-chromosomal genomes
§3.2.2 Transformations on multi-chromosomal genomes
§3.2.2.1 SBRT-limited to internal reversals and translocations
§3.2.2.2 SBRT-the general case
§3.3 Linear algorithm to compute the genomic distance
§3.3.1 A property of a partial set
§3.3.2 The linear algorithm in general case
§3.3.3 The special case -cotailed genomes
§3.4 Conclusion
Chapter 4. Evolution Sequence between Signed Genomes
§4.1 Introduction
§4.2 Preliminaries
§4.2.1 Mimicking multi-chromosomal rearrangements by reversals
§4.2.2 Flipping
§4.3 Faster algorithm for SBRT
§4.3.1 Optimal cappings
§4.3.2 Optimal flipping
§4.3.3 Optimal concatenation
§4.4 Conclusion
Chapter 5. The Translocation Median Problem
§5.1 Introduction
§5.2 The median problem with unsigned data
§5.3 The median problem with signed data
§5.4 Conclusion
Chapter 6. Sorting Binary Strings by Reversals and by Transpositions
§6.1 Introduction
§6.2 Terminology and notation
§6.3 Reversal distance between binary strings
§6.4 Transposition distance between binary strings
Chapter 7. Approximation Algorithm of Protein Similarity Search
§7.1 Introduction
§7.2 Preliminaries
§7.3 Decision version of MRSOS
§7.4 Approximation algorithms for MRSOS-d1
References
Acknowledgements
Curriculum Vitae
学位论文评阅及答辩情况表
发布时间: 2005-10-17
参考文献
- [1].精确控制合成型基因组重排[D]. 贾斌.天津大学2017
- [2].高通量筛选及基因组重排选育维吉尼亚霉素高产菌[D]. 仝倩倩.中国科学技术大学2018
- [3].基因组重排在产纤维素酶斜卧青霉菌种改造中的应用[D]. 程艳飞.山东大学2009
- [4].用基因组重排和进化工程进行菊糖芽孢乳杆菌菌种改进[D]. 郑辉杰.天津大学2009
- [5].始旋链霉菌基因组重排育种、普那霉素发酵条件优化及高产机理分析[D]. 徐波.浙江大学2008
相关论文
- [1].若干组合优化问题的近似算法设计与分析[D]. 陈仕平.浙江大学2002
- [2].计算分子生物学中若干问题研究[D]. 廖波.大连理工大学2004
- [3].基于状态转移的组合优化方法研究[D]. 王正元.国防科学技术大学2004
- [4].不确定优化问题的若干模型与算法研究[D]. 戎晓霞.山东大学2005
- [5].智能优化方法及其应用研究[D]. 钟一文.浙江大学2005
- [6].基于计算智能的若干优化问题研究[D]. 葛宏伟.吉林大学2006
- [7].面向蛋白质结构预测的计算生物学技术研究[D]. 何洁月.东南大学2006
- [8].若干组合优化的智能计算方法与应用研究[D]. 杨金辉.吉林大学2008
标签：基因组重排论文; 多重基因组论文; 移位距离论文; 基因组进化距离论文; 中值问题论文; 排序论文; 蛋白质相似性论文; 近似算法论文;