ISSN 1000-1239 CN 11-1777/TP

• 人工智能 •

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

1. (山东大学计算机科学与技术学院 济南 250101) (liupeixia0629@163.com)
• 出版日期: 2016-03-01
• 基金资助:
国家自然科学基金项目(61202014，61472222)；山东省自然科学基金项目(ZR2012FQ008)；中国博士后科学基金项目(2011M5001133，2012T50614)

### Complexity and Algorithm for Minimum Breakpoint Median from PQ-trees

LiuPeixia,JiangHaitao,ZhuDaming

1. (Shool of Computer Science and Technology, Shandong University, Jinan 250101)
• Online: 2016-03-01

Abstract: A 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 investigate p-Minimum Breakpoint Median from the PQ-tree. Given a PQ-tree and the corresponding p permutations, the goal is to identify a permutation generated by the PQ-tree that holds the minimum breakpoint distances relative to the p permutations. Our study shows that when p≥2, the p-Minimum Breakpoint Median problem from PQ-tree is NP-complete. Moreover, when p=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 is O(3\+Kn) where K is the optimized breakpoint distance.