基因组比较问题的算法与复杂性

基因组比较的核心问题是计算两个基因组的量化距离。本课题讨论基因组重组排序与基因组样本断点距离两个基因组比较问题的算法与复杂性。设计有向基因组Reversal与Translocation排序的局部搜索近似算法；设计有向基因组一般Translocation排序的新精确算法；设计无向基因组Cut-And-Paste排序新近似算法；证明基因组Transposition排序的复杂性；设计基因组短块移动排序的改进近似算法；设计基因组样本断点距离问题的亚指数时间精确算法。力图在上述内容研究中取得新突破。基因组比较算法有助于人们确定基因组的相同与不同区域，充分理解基因的结构与功能，定位控制基因功能的信息，从而找到克服人类疾病的新方法。

本项目研究了一类基因组比较问题的算法与计算复杂性。设计出一组基因组重组排序或基因组重组距离计算问题的近似算法，为项目的标志性结果。基因组重组距离计算是计算比较基因组学的主流分支，近似算法则是解答NP-Hard优化问题的有效手段，也是算法与计算复杂性研究的核心内容。.在国家自然科学基金“基因组比较问题的算法与复杂性(61070019)”的资助下，完成如下主要研究成果：(1)设计出有向基因组一般移位排序的多项式时间算法；(2)设计出无向基因组切割再粘贴排序近似性能比为2.25的多项式时间近似算法；(3)设计出基因组短块移动排序近似性能比为14/11的多项式时间近似算法，进一步设计出整数排列逆序基因对数目足够多时的(1+e)-近似算法；(4)设计出样本断点零距离问题(ZEBD)时间复杂性为O(n^2*1.86^n)的精确算法；(5)设计出单面片段框架填充问题近似性能比为5/4的多项式时间近似算法，设计出双面片段填充问题近似性能比为1.5的多项式时间近似算法；(6)设计出无向基因组交互型移位排序近似性能比为1.408+e的多项式时间近似算法；(7)设计出最大不全k-满足问题的盲目局部搜索近似算法，近似性能比可达到2^(k-1)/(2^(k-1)-1)。已发表学术论文16篇，其中SCI收录11篇，EI收录7篇；期刊论文12篇，会议论文4篇；计算机学会倡导的顶级期刊论文9篇。受邀在全国年会做特邀报告一次。获得山东省自然科学奖3等奖1项，山东大学优秀博士学位论文奖2项。培养博士生6名，硕士生5名。