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

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-难解性为目标。将设计出的新算法实现为生物信息学软件，用于以基因组比较分析为基础的分子生物学和医学研究与实践中。