全基因组结构分析的组合问题与算法

Designing algorithms for combinatorial optimization problems in whole genome structure analysis is an important subject in theoretical computer science. Both genome maximal strip problem and double cut and join rearrangement problem are typical problems in whole genome structure analysis. This project is aiming at: designing new polynomial time approximation algorithms for the maximal strip problem and its complementary problem on genomes without repetition by non-oblivious local search methods, and the approximation factors reach to 3 and 2 respectively; designing a new polynomial time approximation algorithm for the maximal strip problem on genomes with repetitions by linear programming and rounding methods, and the approximation factor reaches to 16/7; designing a new polynomial time 1.375-approximation algorithm and a fixed-parameter time 4/3-approximation algorithm for double cut and join rearrangement problem on unsigned genomes without repetition; designing the first polynomial time approximation algorithm for the problem of breakpoint elimination by double cut and join on genomes with repetitions, with an approximation factor of 1.5. In this project, pursuing better approximation factor is the basic task for designing approximation algorithms. New algorithms of better performance on genome structure analysis problems can have guiding effect on the detection and prediction of genetic diseases.

设计全基因组结构分析中组合问题的算法是理论计算机领域的重要研究内容。基因组最长公共序列问题和二次切割并连接问题都是全基因组结构分析中的典型组合问题。本项目旨在，采用非直接局部搜索技术，设计无重复基因组的最长公共序列原问题和补问题的新多项式时间近似算法，近似性能比分别达到2和3；采用线性规划随机取整技术，设计有重复基因组的最长公共序列问题的新多项式时间近似算法，近似性能比达到16/7；设计无重复无向基因组二次切割并连接问题的近似性能比达到1.375的新多项式时间近似算法，以及近似性能比达到4/3的参数时间近似算法；设计有重复基因组的二次切割并连接断点消除问题的第一个近似算法，近似性能比达到1.5。本项目以竞逐更好的近似性能比作为设计近似算法的根本目标。全基因组结构分析问题的更好性能的新算法，对于遗传疾病的检测和预测具有指导意义。

基因组分析和比较是计算基因组学研究的重要内容之一，对于疾病的检测和预测、探索物种的进化规律有着重要的意义。用计算的方法分析基因组面临的最大挑战是基因组的重复性、不确定性、不完整和存在噪声。为克服这些困难，本项目研究了基因组最长公共序列问题、基因组片段填充问题以及多种模型下的基因组重排问题等典型的组合优化问题。旨在分析证明问题的计算复杂度，设计精确算法或近似算法。主要成果如下：.（1）当基因组都用PQ-树表示时，证明了其断点距离问题和断点中心问题都是NP-难的，并设计了断点距离问题的第一个参数算法。.（2）采用非直接局部搜索技术，设计无重复基因组的最长公共序列补问题的近似性能比为2的多项式时间近似算法。采用线性规划非线性取整技术，设计有重复基因组的最长保守序列问题的近似比为32(k-1)3e3/8e(k-1)-1的近似算法，不证明该问题为APX-hard。.（3）以最大保守对数为优化目标，证明片段填充问题是NP-难的，并设计了近似比为12/7近似算法。以最大公共邻接数为优化目标，设计了近似比为1.4+的近似算法。.（4）对于DCJ模型下的重排问题，设计了有重复序列的近似比为1.44的多项式算法和无重复序列的近似比为4/3的参数时间近似算法。对于移位、有限块移动模型下的重排问题，分别设计了近似比为1.375和3c/5的多项式时间近似算法，其中c表示最大移动距离。.这些问题模型能有效的刻画基因组比较和分析的目标，所设计的算法能有效揭示基因组的潜在性质。.