基因组重排的问题产生于上个世纪七十年代,主要目的是利用已知的DNA数据去确定不同物种之间的相似与差异。基因组重排在比较遗传学中提供了分子进化的一个普遍的模式,它可以对生物学及其他学科提供生物上的有益的刻划。基因组重排问题就是寻找最少数目的进化变换把一个基因组变成另一个基因组。这个最小的进化变换数目称为对应的两个基因组之间的进化距离。我们把求从一个基因组变成另一个基因组的最短的进化变换序列问题称为基因组排序问题。此组合优化问题已成为理论计算机科学与数学领域一个基本的研究课题。基因组重排与蛋白质相似性搜索是近几年来计算生物学中研究的难点与热点。目前有关单染色体基因组的研究比较充分和完善,而有关多染色体基因组的研究不多,并且研究成果很欠缺。本文对多染色体基因组的进化距离计算问题与基因组排序问题进行了研究,着重讨论了与基因组的进化距离有关的算法,给出了问题的最优算法与近似算法,分析了所给算法的复杂性,同时比较了新算法和已有算法,本文的算法都优于已有算法。另外,本文就蛋白质相似性搜索问题,给出了一个相关问题的近似算法和复杂性分析。全文共分七章。