刘培霞　姜海涛　朱大铭

(山东大学计算机科学与技术学院　济南　250101)

(liupeixia0629@163.com)



PQ-树断点距离中心问题的复杂性和精确算法

刘培霞姜海涛朱大铭

(山东大学计算机科学与技术学院济南250101)

(liupeixia0629@163.com)

Complexity and Algorithm for Minimum Breakpoint Median from PQ-trees

Liu Peixia, Jiang Haitao, and Zhu Daming

(ShoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)

AbstractA PQ-tree is a tree-based data structure which can represent large sets of permutations. Although the uncertainty of complete ancestral genomes is known, the homologous species provide information to determine the relative locations of partial genomes, whereby the PQ-tree can be designed to efficiently store ancestral genomes. In evolutionary biology, phylogenetic trees represent the evolutionary relationships between species. In the construction of phylogenetic trees, the leaves of the trees represent current species whose genomes are annotated by permutations, and the internal nodes represent ancestral genomes whose genomes are annotated by PO-trees. In order to determine the evolutionary relationships between different species, it is necessary to quantify the distances between the known permutations and the permutations in the constructed PQ-trees. Based on the measurement of breakpoint distance, we investigatep-Minimum Breakpoint Median from the PQ-tree. Given a PQ-tree and the correspondingppermutations, the goal is to identify a permutation generated by the PQ-tree that holds the minimum breakpoint distances relative to theppermutations. Our study shows that whenp≥2, thep-Minimum Breakpoint Median problem from PQ-tree is NP-complete. Moreover, whenp=1, the problem is fixed parameters tractable. To solve the 1-Minimum Breakpoint Median from PQ-trees, we propose a Fixed-Parameter Tractable algorithm whose computation complexity isO(3Kn) whereKis the optimized breakpoint distance.

Key wordsPQ-tree; breakpoint distance; fixed-parameter tractable; permutation; NP-complete

摘要PQ-树是一种树状数据结构，用来表示元素排列集合.虽然消逝物种完整基因组序列具有不确定性，但是根据同源物种可以确定部分基因的相对位置，所以可以利用PQ-树来存储消逝物种的基因组.在生物学中，进化树用来表示物种之间的进化关系.当构建生物进化树时，叶子结点表示现存物种，其基因组用排列表示；内部结点为祖先物种，其基因组用PQ-树表示.为了确定物种间的进化关系，需要确定PQ-树可以产生的排列与已知排列之间的距离.以断点距离为标准，研究了p-PQ-树断点中心问题，即从给定PQ-树中产生一个排列，使之与给定的p个排列的断点距离之和最小.证明当p≥2时，p-PQ-树断点中心问题是NP-完全的.当p=1时，p-PQ-树断点中心问题是参数化可计算的，针对1-PQ-树断点中心问题，提出了时间复杂度为O(3Kn)的参数化算法，其中K为最优解的断点距离.

关键词PQ-树；断点距离；固定参数可解；排列；NP-完全

PQ-树是由Kellogg和George[1]发现并命名的一种树状数据结构，可以用来表示元素排列的集合.PQ-树主要用来解决一些目标是寻找满足各种约束的排列的问题，在这些问题中，通过一次添加一种约束的方式编辑PQ-树的结构，使得编辑后的PQ-树能表示满足约束的排列.PQ-树的主要应用有：验证矩阵是否具有连续1性质[1]、判……