| PQ-树断点距离中心问题的复杂性和精确算法 |
| |
| 引用本文： | 刘培霞, 姜海涛, 朱大铭. PQ-树断点距离中心问题的复杂性和精确算法[J]. 计算机研究与发展, 2016, 53(3): 644-650. DOI: 10.7544/issn1000-1239.2016.20148258 |
| |
| 作者姓名： | 刘培霞 姜海涛 朱大铭 |
| |
| 作者单位： | (山东大学计算机科学与技术学院 济南 250101) (liupeixia0629@163.com) |
| |
| 基金项目： | 国家自然科学基金项目(61202014,61472222);山东省自然科学基金项目(ZR2012FQ008);中国博士后科学基金项目(2011M5001133,2012T50614) |
| |
| 摘 要： | PQ-树是一种树状数据结构,用来表示元素排列集合.虽然消逝物种完整基因组序列具有不确定性,但是根据同源物种可以确定部分基因的相对位置,所以可以利用PQ-树来存储消逝物种的基因组.在生物学中,进化树用来表示物种之间的进化关系.当构建生物进化树时,叶子结点表示现存物种,其基因组用排列表示;内部结点为祖先物种,其基因组用PQ-树表示.为了确定物种间的进化关系,需要确定PQ-树可以产生的排列与已知排列之间的距离.以断点距离为标准,研究了p-PQ-树断点中心问题,即从给定PQ-树中产生一个排列,使之与给定的p个排列的断点距离之和最小.证明当p≥2时,p-PQ-树断点中心问题是NP-完全的.当p=1时,p-PQ-树断点中心问题是参数化可计算的,针对1-PQ-树断点中心问题,提出了时间复杂度为O(3\\+Kn)的参数化算法,其中K为最优解的断点距离.
|
| 关 键 词： | PQ-树 断点距离 固定参数可解 排列 NP-完全 |
|
| 点击此处可从《计算机研究与发展》浏览原始摘要信息 |
|
点击此处可从《计算机研究与发展》下载免费的PDF全文 |
|
