通过交互式移位-插入-删除进行基因组排序的较快算法

作     者：郝凡昌 栾峻峰 朱大铭 张鹏 李明 Hao Fanchang;Luan Junfeng;Zhu Daming;Zhang Peng;Li Ming

作者机构：山东大学计算机科学与技术学院济南250101 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2010年第47卷第11期

页      面：2011-2023页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(60970003) 教育部博士学科点专项科研基金项目(20090131110009) 国家"九七三"重点基础研究发展计划基金项目(2005cca04500) 山东省优秀中青年科学家奖励基金项目(BS2009DX009) 

主　　题：基因重组 交互式移位 插入 删除 距离公式 算法 

摘      要：多染色体基因组进化问题中常见的重组事件就是移位(translocation),对此已有很多研究成果.但事实上更为普遍的情况是2个基因组包含不同基因,这需要考虑插入和删除事件.对于通过移位-插入-删除进行基因组排序(简称SG-TID)这个问题,此前已有一个求解移位-删除(或者移位-插入)序列的近似算法,以及求解SG-TID问题的启发式算法.在给出了移位-插入-删除距离的表达公式后,给出了在增加O(n)存储空间的条件下,O(n2)时间内求解该问题的精确算法.该算法比此前给出的算法要快.