Complexity and Algorithm for Minimum Breakpoint Median from PQ-trees
-
摘要: PQ-树是一种树状数据结构，用来表示元素排列集合.虽然消逝物种完整基因组序列具有不确定性，但是根据同源物种可以确定部分基因的相对位置，所以可以利用PQ-树来存储消逝物种的基因组.在生物学中，进化树用来表示物种之间的进化关系.当构建生物进化树时，叶子结点表示现存物种，其基因组用排列表示；内部结点为祖先物种，其基因组用PQ-树表示.为了确定物种间的进化关系，需要确定PQ-树可以产生的排列与已知排列之间的距离.以断点距离为标准，研究了p-PQ-树断点中心问题，即从给定PQ-树中产生一个排列，使之与给定的p个排列的断点距离之和最小.证明当p≥2时，p-PQ-树断点中心问题是NP-完全的.当p=1时，p-PQ-树断点中心问题是参数化可计算的，针对1-PQ-树断点中心问题，提出了时间复杂度为O(3\+Kn)的参数化算法，其中K为最优解的断点距离.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.
-
Keywords:
- PQ-tree /
- breakpoint distance /
- fixed-parameter tractable /
- permutation /
- NP-complete
-
-
期刊类型引用(15)
1. 王靖，方旭明. Wi-Fi7多链路通感一体化的功率和信道联合智能分配算法. 计算机应用. 2025(02): 563-570 . 
百度学术
2. 葛振兴，向帅，田品卓，高阳. 基于深度强化学习的掼蛋扑克博弈求解. 计算机研究与发展. 2024(01): 145-155 . 本站查看
3. Xiaodong Zhuang，Xiangrong Tong. A dynamic algorithm for trust inference based on double DQN in the internet of things. Digital Communications and Networks. 2024(04): 1024-1034 . 必应学术
4. 李迎港，童向荣. 基于知识引导的自适应序列强化学习模型. 模式识别与人工智能. 2023(02): 108-119 . 百度学术
5. 冯景瑜，张静，时翌飞. 物联网中具备终端匿名的加密流量双层过滤方法. 西安邮电大学学报. 2023(02): 72-81 . 百度学术
6. 冯景瑜，李嘉伦，张宝军，韩刚，张文波. 工业互联网中抗APT窃密的主动式零信任模型. 西安电子科技大学学报. 2023(04): 76-88 . 百度学术
7. 丁世飞，杜威，郭丽丽，张健，徐晓. 基于双评论家的多智能体深度确定性策略梯度方法. 计算机研究与发展. 2023(10): 2394-2404 . 本站查看
8. 冯景瑜，王锦康，张宝军，刘宇航. 基于信任过滤的轻量级加密流量异常检测方案. 西安邮电大学学报. 2023(05): 56-66 . 百度学术
9. 徐敏，胡聪，王萍，张翠翠，王鹏. 基于强化学习的Ceph文件系统的性能优化. 微型电脑应用. 2022(03): 83-86 . 百度学术
10. 冯景瑜，于婷婷，王梓莹，张文波，韩刚，黄文华. 电力物联场景下抗失陷终端威胁的边缘零信任模型. 计算机研究与发展. 2022(05): 1120-1132 . 本站查看
11. 王鑫，赵清杰，于重重，张长春，陈涌泉. 多节点探测器软着陆的路径规划方法. 宇航学报. 2022(03): 366-373 . 百度学术
12. 张文璐，霍子龙，赵西雨，崔琪楣，陶小峰. 面向智能工厂多机器人定位的无线分布式协同决策. 无线电通信技术. 2022(04): 718-727 . 百度学术
13. 王岩，童向荣. 基于tri-training和极限学习机的跨领域信任预测. 计算机研究与发展. 2022(09): 2015-2026 . 本站查看
14. 聂雷，刘博，李鹏，何亨. 基于多智能体Q学习的异构车载网络选择方法. 计算机工程与科学. 2021(05): 836-844 . 百度学术
15. 洪志理，赖俊，曹雷，陈希亮. 融合用户兴趣建模的智能推荐算法研究. 信息技术与网络安全. 2021(11): 37-48 . 百度学术
其他类型引用(15)
计量
- 文章访问数:
- HTML全文浏览量: 0
- PDF下载量:
- 被引次数: 30
下载:
