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

项目名称： 基因组比较中三个组合问题的算法研究

项目编号： No.61202014

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 姜海涛

作者单位： 山东大学

项目金额： 24万元

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

中文关键词： 算法；NP-完全；近似性能比；；

英文摘要： 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

英文关键词： Algorithm；NP-Complete；Approximation Factor；；