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

项目编号: 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

成为VIP会员查看完整内容
0

相关内容

在数学和计算机科学之中,算法(Algorithm)为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。 来自维基百科: 算法
【干货书】算法设计艺术,319页pdf
专知会员服务
112+阅读 · 2021年10月24日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
【经典书】半监督学习,524页pdf
专知会员服务
134+阅读 · 2021年8月20日
专知会员服务
15+阅读 · 2021年8月6日
【经典书】机器学习统计学,476页pdf
专知会员服务
118+阅读 · 2021年7月19日
【经典书】数据结构与算法,770页pdf
专知会员服务
133+阅读 · 2021年4月15日
【经典书】R机器学习入门:严格的数学分析,225页pdf
专知会员服务
61+阅读 · 2021年2月16日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
74+阅读 · 2020年12月6日
【清华大学龙明盛副教授】迁移学习理论与算法,59页ppt
专知会员服务
80+阅读 · 2020年11月27日
缺陷检测的传统算法与深度学习算法
CVer
1+阅读 · 2022年4月13日
【极市打榜|算法上新】人员检测识别
极市平台
1+阅读 · 2022年2月23日
综述:图像滤波常用算法实现及原理解析
极市平台
0+阅读 · 2022年1月29日
不断发展的强化学习算法
TensorFlow
2+阅读 · 2021年5月20日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月20日
Arxiv
0+阅读 · 2022年4月20日
Arxiv
0+阅读 · 2022年4月19日
Arxiv
0+阅读 · 2022年4月19日
Arxiv
19+阅读 · 2018年6月27日
Arxiv
11+阅读 · 2018年4月25日
小贴士
相关VIP内容
【干货书】算法设计艺术,319页pdf
专知会员服务
112+阅读 · 2021年10月24日
算法分析导论, 593页pdf
专知会员服务
144+阅读 · 2021年8月30日
【经典书】半监督学习,524页pdf
专知会员服务
134+阅读 · 2021年8月20日
专知会员服务
15+阅读 · 2021年8月6日
【经典书】机器学习统计学,476页pdf
专知会员服务
118+阅读 · 2021年7月19日
【经典书】数据结构与算法,770页pdf
专知会员服务
133+阅读 · 2021年4月15日
【经典书】R机器学习入门:严格的数学分析,225页pdf
专知会员服务
61+阅读 · 2021年2月16日
专知会员服务
69+阅读 · 2020年12月7日
专知会员服务
74+阅读 · 2020年12月6日
【清华大学龙明盛副教授】迁移学习理论与算法,59页ppt
专知会员服务
80+阅读 · 2020年11月27日
相关资讯
缺陷检测的传统算法与深度学习算法
CVer
1+阅读 · 2022年4月13日
【极市打榜|算法上新】人员检测识别
极市平台
1+阅读 · 2022年2月23日
综述:图像滤波常用算法实现及原理解析
极市平台
0+阅读 · 2022年1月29日
不断发展的强化学习算法
TensorFlow
2+阅读 · 2021年5月20日
相关基金
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
微信扫码咨询专知VIP会员