计算机学院姜海涛副教授在IandC发表论文解决PQ-树相关问题

发布日期:2020-04-13 字号:  点击次数:

近日,计算机科学与技术学院姜海涛副教授作为第一作者在理论计算机科学领域顶级期刊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

【 作者:姜海涛  来源:计算机学院   责任编辑:荆子曌 】

上一条:微生物技术国家重点实验室在青岛蓝谷的首个产学研项目正式投产

下一条:生命学院郑培明课题组在生活垃圾分类回收和资源利用领域取得新进展

请遵守《互联网电子公告服务管理规定》及中华人民共和国其他有关法律法规。
用户需对自己在使用本站服务过程中的行为承担法律责任。
本站管理员有权保留或删除评论内容。
评论内容只代表网友个人观点,与本网站立场无关。
 匿名发布 验证码 看不清楚,换张图片
0条评论    共1页   当前第1
最新新闻

办公地址:山东省青岛市即墨滨海路72号   邮编:266237     E-mail:rmtzxqd@sdu.edu.cn        

版权所有@山东大学   鲁ICP备案 05001952号   

访问量: