随着对基因组的研究深入和逐渐破译,我们的生活发生了巨大的变化。尤其是在医疗界中,随着人们对于基因组的了解迈上了新台阶,很多疾病的病因被逐渐的揭开,医务工作者在设计药物时能够更加科学有效,从而使得通过基因疗法来治疗一些当前医疗手段还无法治愈的疾病成为现实。通过控制人类的某些生化特性,从而达到恢复或者修复人体细胞和器官功能的目的,因此通过对基因组信息的操作甚至可以改变人类的进化过程。在农作物领域,人们可以通过控制基因组来改良果蔬品种,从而快速的提高农作物的品质,我们可以预见将会有越来越多的转基因植物、动物和食品问世,在新世纪里人类可能培养出超级作物。由此可见,在科技发展如此迅猛的今天,对于基因组的研究已然成为医疗、作物等多个生物科研领域中一个十分重视的问题。应运而生的则为计算生物学,科学家们通过数学建模和计算机仿真计算等方式对基因组中的相关操作进行分析,对基因组数据进行处理并从中获取生物信息。其中,典型的问题包括计算基因组间的重组距离、基因组片段的拼接、通过生物测序技术来得到基因组序列中冗余或丢失的信息等。但是由于基因庞大的数目、突变导致的相似性等问题的存在,当前对于计算生物领域的绝大部分问题都是NP-难的,这就要求计算生物领域的研究者们更多的致力于设计出多项式时间近似算法。本文主要针对计算基因组间的重组距离、基因组片段的拼接两类问题进行了分析讨论。对于排列短块移动排序距离问题,使用了基因组重排操作中的转位操作。次转位操作也称为一次块移动。短块移动是最常见的一种块移动。一次短块移动是将一个元素从排列中某个位置移动到最多偏离原来两个位置的块移动,因此也称为3-bounded转位。针对排列短块移动排序距离问题,文中给出了一类称之为双递增排列的特殊的排列,并得出了其短块移动排序次数的下界。以此为依据,分析原始排列中的所有最大双递增子排列,从而给出了任意排列短块移动排序次数的下界,改进了Heath和Vergara的负面结果,并为更好的近似算法的设计打下基础。而对于基于A-Bruijn图的基因组序列拼接问题,本文对Pevzner提出的用于解决单一基因组序列的RepeatGluer算法进行了详细的解释说明,此算法对基于A-Bruijn图的基因组副本进行分组。最后给出了相关步骤的部分代码,以期能够通过对A-Bruijn图的学习与实现,更好的了解并探讨解决基因组序列拼接问题的方法。