随着生物技术的发展和计算机科技的进步,生物信息学这个生物和计算机的交叉学科越来越引起人们的注意。生物信息学可以理解成计算机技术在生物上的应用。比较基因组学是生物信息学中的一个重要研究领域。自从九十年代末期,比较基因组学开始逐步兴起,迄今已经走过将近二十年的历程。比较基因组学传统的研究假设是两条基因组不包含重复基因,这种假设在部分病毒和线粒体的基因组中是成立的,但是对于哺乳动物和植物等,这种假设是不满足的。据估计人类的基因组中有15%的基因是含有重复的[49]。样本断点距离问题的研究就是在基因组包含重复的假设下进行的。寻找两条基因组之间的保留基因集合是基因组比较中的一个基本问题。在基因组中以相同顺序保存的一组基因暗示它们参与相同的生物过程。为了寻找基因组中保留基因集合,人们提出许多相似性度量,例如,断点数目,邻接数目,保留区间数目和公共区间数目。当基因组不包含重复基因时,所有这些距离都能很好定义。然而,基因复制是基因组进化的主要驱动力之一,并且频繁发生(Dennis等,2012)。当复制发生时,一个基因可能出现在一条基因组中的几个不同地方。样本断点距离问题是受寻找两条基因组之间保留基因集合启发提出的一个问题。它询问寻找两条基因组各自的样本,以满足样本之间的断点距离最小。如果一条基因组没有重复基因(称为平凡基因组)并且另一条基因组的每个基因至多出现两次,它被称为(1,2)-样本断点距离问题,简称为EBD(1,2)。虽然EBD(1,2),作为最基本的样本断点距离问题,已知为APX-Hard多年,但在算法设计方面却做得很少。事实上,EBD(1,2)是否存在固定参数算法直到现在都是未知的。Zhu(2009)指出如果参数是样本断点距离,EBD(2,2)不存在任何固定参数算法[34]。这让EBD(1,2)是否存在基于某个参数的固定参数算法变得更加有趣。针对EBD(1,2)的固定参数算法,本文重点进行了以下研究工作：(1)我们利用非平凡基因组的跨度(span),记为s,作为参数,设计EBD(1,2)的第一个固定参数算法,其中引入基因组的跨度(span)这个概念来表示基因组中同一基因家族的两个基因横跨的最多基因数目。这取决于一个实际观察,这个观察是在一条基因组中同一基因家族的两个基因通常被少量基因所分隔(Shi等,2010)[31]。对于一个每条基因组包含n个基因家族的EBD(1,2)实例,我们的算法可以在O(4Sn2)时间内和O(4Sn)空间内运行。这在之前是未见的。(2)我们用C++语言实现了上述算法。在随机产生数据上的仿真表明,当基因组的跨度为10,我们的算法总是可以在1000秒内处理包含5000个基因家族的基因组,并且当基因组的跨度为15,我们的算法可以在1600秒内处理包含1000个基因家族的基因组。我们算法的软件包可以在如下网址获取：http://www.cs.sdu.edu.cn/dmzhu/exemplar-distance/software.html基于串联质谱的肽从头测序问题是本文作者的早期研究问题。基于串联质谱的肽从头测序问题是蛋白质组学领域中蛋白质识别最常用的方法之一,它在没有蛋白质数据库辅助的情况下,直接由未知肽P的串联质谱识别出其氨基酸序列。肽从头测序一般将未知肽P的串联质谱转换为一个质谱图G,通过在图G中寻找合适路径的方法来识别出未知肽P的氨基酸序列。图G中的一条路径代表一条可能的肽,我们希望找出与未知肽P尽可能相似的一条或多条肽。在质谱图G的构造过程中,由于不知道串联质谱中的每个峰值p对应的是未知肽P的前端子序列,还是后端子序列,因此在质谱图G中,每个峰值p用两个顶点v和v表示。其中、,表示峰值p对应的是前端子序列,v表示峰值p对应的是后端子序列,但用未知肽P减去后端子序列,我们得到前端子序列。这样,对于每个峰值p,不管它是前端子序列,还是后端子序列,我们总是可以在质谱图G中用一个顶点来表示这个峰值p对应的未知肽P的前端子序列。因为图中的每个顶点表示未知肽P的某个前端子序列,如果任意两个顶点对应质量值相减等于一个或几个氨基酸的质量值,表示这两个前端子序列相差一个或几个氨基酸。Dancik等[39]为质谱图G设计了一种加权算法,并通过在加权质谱图中寻找最长路径的方法来得到与未知肽P最相似的肽。但他们注意到同时经过v和v的最长路径是毫无意义的。因为一个峰值p不可能既是未知肽P的前端子序列又是后端子序列。这样问题转化为寻找不能同时经过一些顶点对的最长路径问题。称不能同时经过的顶点对为禁止顶点对。因为避免禁止顶点对的路径问题是NP-Hard的,所以避免禁止顶点对的最长路径问题也是NP-Hard的。Dancik等和Chen等又注意到因为每个顶点都对应一个质量值,实际上顶点是有序的,可以将它们从左向右画在数轴上,对于任意两对禁止顶点对(v1,v1)和(v,v2),(v1,v1)对应的区间段和(v2,v2)对应的区间段是嵌套的。针对基于串联质谱的肽从头测序问题,本文重点进行了以下研究工作：(1)基于串联质谱的肽从头测序问题可以转化为避免禁止顶点对的最长路径问题(PAFP)。一般的PAFP问题是NP-Hard的。但是从肽从头测序到PAFP问题的转化过程中,禁止顶点对具有嵌套结构。基于禁止顶点对的嵌套结构,我们给出求解肽从头测序问题的一种顶点收缩算法。顶点收缩算法是一种多项式时间算法,其时间复杂度为D(|V|3)。