基因组比较中三个组合问题的算法研究

Computing the distance between two genomes is one of the most important subjects in the area of genome comparison and rearrangements. The breakpoint distance is a basic measure for comparing two genomes; and the translocation operation is one of the classic genome rearrangement operations. In this subject, we will conduct a systematic research on the scaffold filling under breakpoint and related distance problem, the PQ-trees similarity comparison under the breakpoint distance problem and the sorting unsigned genome by translocations problem in the framework of approximation algorithm and fix-parameter tractability. we will,(1)devise the first non-trivial approximation for the two-side scaffold filling for genome with gene repetitions problem, improve the approxiamtion factor for the one-side scaffold filling for genome with gene repetitions problem, and prove the inapproximability of both the two problems;(2) prove that the PQ-tree median problem is NP-complete, and improve the time complexity of the fixed-parameter algorithm; (3)for the sorting unsigned genomes by translocations problem, devise the first fixed-paremeter algorithm and improve the approxiamtion factor. . Algorithms on genome comparison can contribute to the simplification of whole-genome sequencing. According to the distinct areas between two genomes, it would be possible to determine the pathogenic genes, which develops a new method to conquer some genetic diseases.

计算基因组距离是基因组比较和重组研究的重要内容之一。断点距离是最基本的基因组比较量化依据；移位距离是经典的基因组重组距离量化形式之一。本课题中讨论基因组片段填充的断点距离问题、基因组PQ-树的相似性比较问题和基因组移位重组距离问题的算法和计算复杂性。(1)设计有重复基因组双面填充的第一个非平凡近似算法，改进有重复基因组单面填充的近似算法的近似比，并证明有重复基因组片段填充的不可近似性；(2)证明基因组PQ-树断点中心问题是NP-完全的，并改进基因组PQ-树断点中心问题的参数化算法的时间复杂度；(3)设计无向基因组移位排序问题的第一个参数化算法，并改进该问题近似算法的近似比。力图在上述内容研究中取得新进展。基因组比较算法有助于简化全基因组测序过程，依据基因组上的相同和不同区域，快速定位致病基因并充分理解其结构与功能，为遗传疾病的基因治疗提供新思路。

基因组的比较与重组是计算基因组学研究的重要内容之一，对于探究物种间的进化规律，分析基因的功能都有着重要的指导意义。本项目中，重点研究了基因组比较中的三个组合优化问题：（1）基因组序列的片段填充问题；（2）基因组PQ-树的相似性比较问题；（3）基因组排列的移位重组排序问题，并拓展研究了：（4）基因组排列的短块移动排序问题；（5）基因组最长带恢复问题。对上述问题，从计算复杂性、多项式时间近似算法、参数算法、核心化等分析解决NP-困难问题的角度进行了深入研究，取得了的研究成果如下：.（1）提出以最大化公共邻接数为优化目标的基因组序列片段填充问题，并证明了最优填充方案的公共邻接数的下界。设计了单面片段填充问题的近似性能比为4/3的近似算法；后来又将近似性能比依次改进至5/4和6/5，并证明该问题是APX-hard的。设计了双面片段填充问题的近似性能比为3/2的近似算法。（2）证明了基因组PQ-树断点中心问题是NP-完全的，并对于比较一棵PQ-树基因组和一个排列的特殊问题，设计了时间复杂度为O*(3K)的参数算法。（3）将基因组移位排序问题的近似算法的近似性能比改进至1.408+e。（4）证明了基因组短块移动排序问题最优解的更紧下界，并设计了近似性能比为5/4的近似算法。（5）证明基因组最长带恢复问题存在大小为18K的亚核和78K的核。.证明问题的计算复杂性可以从理论上说明求解问题的困难程度，近似性能比和时间复杂度分别是评估近似算法和参数算法优劣的量化指标。项目中的绝大多数研究成果还是当前解决该问题的最好结果，我们也一直期待着和致力于研究出更好的成果。