计算生物学中有关基因组距离问题研究.pdf

山东大学博士学位论文计算生物学中有关基因组距离问题研究姓名：栾峻峰申请学位级别：博士专业：运筹学与控制论指导教师：马绍汉山东大学博士学位论文计算生物学中有关基因组距离问题研究摘要计算生物学是现今世界的热门学科，计算生物学研究的有关成果直接影响着人类在生物进化、基因制药等领域的研究进展。生物学、化学、数学、计算机科学等各领域专家学者都在关注着计算生物学的发展。世纪年代末，及其同事在对比甘蓝与芜箐甘蓝的基因序列时发现，排列形成两种基因序列的分子几乎完全相同，只是这些分子在两种基因中的排列顺序不一样。这一发现以及其后的研究表明，基因重组是生物演化过程中的一个基本特征。自此以后，与基因重组有关的技术与理论研究成为计算生物学研究中的一个热点，其在生物种进化研究、生物分类学研究、生物制药研究等研究领域中显示出重要的研究价值““。基因重组对于计算机科学理论研究来说，其基本课题是基因组距离的计算问题，以及基于基因组距离计算的进化树问题。基因组距离主要为基因序列之间的距离(距离、翻转距离)和基因组之间的距离(一距离)。目前，基于基因组距离计算的各种进化树问题是理论研究的热点与难点啪侧。和均是十分复杂的生物进化过程，将这些过程归结为简单的基因组重组模型，提出排序和排序问题，并统称为基因组重组排序问题“‘。本文就与基因组重组排序有关的距离计算问题进行研究，得到三个主要结果：()证明基于基因组距离自幄树问题是难解的，证明该问题不存在绝对近似算法，并给出一个该问题的近似性能比为的近似算法””。基因组距离星树问题是基因组进化树问题中的最基本问题，其难解性预示着其它进化树问题的求解也是十分困难的；()进一步研究证明固定基因序列符号顺序的叶星树问题是难解的，并给出近似性能比为的近似算法“‘”；同时证明对于叶星树问题，不需固定基因序列符号顺序，也是难解的’。基因组距离星树问题实例中给定基因序列条数为变量，将变量改为常数或在算法复杂性理论研究中是一个质的变化，本结论进一步完善了星树问题的计算复杂性分析：