基因组比较与分析算法研究

The reversal or translocation sorting, the short block move sorting, the exemplar breakpoint distance,and the scaffold filling, are all typical combinatorial problems in comparison and analysis of genomes. In this project, we will design two new approximation algorithms, respectively for sorting unsigned genomes by reversals and sorting unsigned genomes by translocations to find better solutions; design a new algorithm for sorting genomes by short block moves to find better solutions, then prove its complexity;design a deterministic exact and a randomized algorithm to improve the time complexity to a lower bound for the zero exemplar breakpoint distance problem, then design a parameterized algorithm for the exemplar breakpoint distance problem; design a new approximation algorithm for the single sided scaffold filling to find better solutions,then prove the complexity of a sub problem of it and design an approximation algorithm to find better solutions than that the algorithm can find for its general version, and design a new approximation algorithm to find better solutions for the two sided scaffold filling. The algorithmic contents of this project always aim to design algorithms to achieve better performance measures, while the complexity approaches aim to prove those problems which are open for their complexity to be NP-Hard. We will manufacture softwares based on the newly designed algorithms, in order to be used in the researches and practices of mocular biology and medical science.

翻转与移位排序、短块移动排序、样本断点距离、和片段框架填充，均为基因组比较与分析的代表性问题。设计无向基因组翻转和移位排序问题的新近似算法，改进算法的近似性能比；设计基因组短块移动排序的改进近似算法，证明该问题的复杂性；设计零样本断点距离问题的确定精确算法和随机求解算法，改进算法的时间复杂性，设计样本断点距离问题的实用参数算法；设计单面片段框架填充问题的新近似算法，改进算法近似性能比；证明单面片段框架填充问题子问题的复杂性，设计其近似算法；设计双面片段框架填充问题的改进近似算法。算法设计均以达到以前未曾达到的量化性能指标为目标，复杂性研究则以证明目前尚未确定复杂性问题的NP-难解性为目标。将设计出的新算法实现为生物信息学软件，用于以基因组比较分析为基础的分子生物学和医学研究与实践中。

项目研究内容以基因组结构比较分析为背景。研究基因组结构差异分析的组合优化问题模型，和解答问题的算法。.将无向基因组移位排序的近似性能比由1.408改进为1.375。设计出无向断点图2-圈分解的多项式时间算法，解决了一个开放20年的基因组重排研究中的基本问题。设计出基因组双面片段填充近似性能比为1.5的多项式时间近似算法，并将近似性能比进一步改进为1.4+e。设计出(1,2)-样本断点距离问题的新动态规划算法，最长样本公共子序列问题的新动态规划算法。最长样本公共子序列用于表示基因组保守子序列，在基因组功能分析研究中具有重要意义。设计出基因组短交换排序问题判定版本的多项式算法，解决了开放10年的基因组比较领域的典型问题。给出转录组组装新算法，计算精度和运算时间好于原有算法。给出一个利用自顶向下蛋白质质谱数据，鉴定蛋白质的有向图模型。这一模型可有效避免鉴定过程中的蛋白质丢失问题，并能保证计算速度。在国家自然科学基金资助下，于2016年举办了第十届国际算法前沿年会(FAW2016)，于2018年举办了第24届国际计算与组合年会(Cocoon2018)。发表期刊论文11篇，SCI收录10篇，国际会议论文15篇。