计算生物学是一门综合性很强的学科,它涉及到生物学、计算机科学等多种内容。根据达尔文的生物进化论,普遍认为物种之间存在一种遗传系谱关系,为了生动形象的描述物种之间的遗传系谱关系,科学家们提出了生物进化树。生物进化树是一种树状图表,在生物进化树的分支上,存放的是能代表不同物种的结构或者信息。但在构建生物进化树时,采用何种信息来代表生物物种是值得人类思考的问题,现在普遍认可采用基因组序列代表对应物种来构建生物进化树。伴着生物实验水平的提升,人们利用各种实验手段得到了大量的基因组数据,这些基因组数据对于研究生物进化史有着不可或缺的作用。鉴于此,科学家们提出了利用基因组数据来作为生物进化树的构成元素。在构建生物进化树时,要根据不同物种基因组序列的相似程度来衡量基因组序列所对应物种之间的亲缘关系的远近。对于祖先物种基因组,由于祖先物种已经消逝,人类无法得到祖先物种完整基因组,只能利用现有技术得到祖先物种基因组片段,推测祖先物种基因组中的连续遗传区。因此,在存储祖先物种基因组时,要考虑祖先物种基因组的特点,本文利用PQ-树可以表示排列的集合的特性,采用PQ-树来存储祖先物种基因组,而对于现有物种基因组,则用排列表示。不同物种之间的同源性与物种基因组序列的相似程度有着极大的关系,因此,可以通过比较不同物种基因组序列之间的相似程度,从而了解物种的进化。在衡量不同物种基因组序列的相似程度时,利用序列比对的方法来判定基因组序列之间的差异。在基因组序列比较时,要有一定的标准来量化基因组序列之间的相似程度,本文中,将以断点距离为标准,衡量物种基因组序列的相似程度。在生物进化树中,叶子结点表示现有物种基因组,本文中采用排列表示,内部结点表示祖先物种基因组,本文采用PQ-树结构存储,鉴于祖先物种基因组与现有物种基因组基本组成元素相同,因此PQ-树中叶子结点所表示的元素与排列中含有的元素也相同。为了判断祖先物种与现有物种之间的进化关系,需要衡量祖先物种基因组与现有物种基因组之间的相似程度,即需要求解PQ-树所表示的排列与已知排列之间的距离。本文中,采用断点距离为标准,分析并求解p排列PQ-树断点中心问题。本文主要工作内容如下：1、对p排列PQ-树断点中心问题的复杂性进行了分析以及证明,结论为当p≥2时,该问题的复杂性是NP-完全的。2、本文将证明1排列PQ-树断点中心问题是参数化可计算的,并且本文将针对该问题提出参数化算法,并实现跟验证该算法。