通过交互式移位-插入-删除进行基因组排序的较快算法
A Faster Algorithm for Sorting Genomes by Reciprocal Translocation,Insertion and Deletion作者机构:山东大学计算机科学与技术学院济南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)时间内求解该问题的精确算法.该算法比此前给出的算法要快.