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

项目名称： 基因组比较与分析算法研究

项目编号： No.61472222

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 朱大铭

作者单位： 山东大学

项目金额： 83万元

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

中文关键词： 算法；计算复杂性；近似性能比；基因组；断点

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

英文关键词： Algorithm;Computational Complexity;Approximation Ratio;Genome;Breakpoint