［本站讯］近日，计算机科学与技术学院姜海涛副教授作为第一作者在理论计算机科学领域顶级期刊IandC（Information and Computation）上发表文章“Breakpoint distance and PQ-trees”，揭示了PQ-树所产生的排列的断点距离特性，解决了比较基因组学领域的两个十几年来悬而未决的公开问题。山东大学为该论文的第一作者单位，美国Montana State University和加拿大Simon Fraser University为合作单位。

PQ-树是一种基本的“树状”数据结构，它包含P和Q两种树结点，其中P结点的后代节点可自由排列，Q结点的后代结点只有正反两种顺序。因此，它能用以有限的空间（O(n)）存储大量（指数级）的排列。现已被广泛应用于平面图判定、矩阵连续1性质判定、基因组片段映射等方面。

当PQ-树被用来存贮非确定性的基因组排列时，如何从PQ-树中产生一个与已知排列最相似的基因组排列（PQ-树断点中心问题）？如何从两个PQ-树中产生两个最相似的排列（PQ-树断点距离问题）？这是两个比较基因组学的亟待解决的典型组合优化问题，其计算复杂性一直未知。

在姜海涛副教授发表的论文中，以最基本的断点距离作为两个排列相似性的评价指标，采用Karp归约，分别证明了这两个问题都是NP-困难的。对两个公开问题的计算复杂性，给出确切的回答。这意味着，在P¹NP的前提下，这两个问题都不存在多项式时间的精确算法。从而，使后续的近似算法和参数算法的研究变得有意义。同时，论文中对于PQ-树断点中心问题，设计了第一个参数算法，证明了该问题的参数可解性。

IandC是中国计算机学会认定的理论计算机科学领域的A类顶级期刊。理论计算机科学以“图灵机”为现代计算机的理论模型，研究关于计算复杂性、算法、计算逻辑等计算机科学的基础理论问题，有十几位“图灵奖”得主从事这个领域。研究工作难度大，论文发表周期长。IandC在2017年、2018年和2019年发表正刊论文分别为45篇、37篇和43篇，其中来自国内科研单位的论文仅为5篇、3篇、4篇，论文作者来自于上海交通大学、南京大学、北京大学、中科院软件所等著名高校和科研院所。本项研究是山东大学计算机科学与技术学院首次在理论计算机科学方向CCF-A类期刊上发表论文。该项研究工作得到国家自然科学基金重点项目、国家自然科学基金面上项目和山东大学青年学者“未来计划”项目的支持。

姜海涛副教授所在的理论计算机科学研究团队成立于上世纪八十年代，先后在马绍汉教授、朱大铭教授的带领下，一直处于国内理论计算机科学领域前列。近年来，在ACM Trans. on Algorithms, Journal of Computer and System Sciences, Algorithmica, Theoretical Computer Science等理论计算机科学领域的重要期刊发表论文20余篇。

文章链接：Breakpoint distance and PQ-trees