枚举有符号基因组的可行交互移位算法

• 作者: 栾峻峰 陈超
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 基因组重组 交互移位排序 移位距离
• 年，卷（期）: 2010,（9）
• 页码范围: 152-156
• 分类号: TP301.6
• 字数: 6752字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2010.09.040

摘要

交互移位排序问题(SRT)是寻找一个使一个基因组转变为另一个基因组的最短交互移位序列.现在已有多个多项式时间的SRT算法,但大多数问题实例都有许多个最短交互移位序列,因此寻找所有最短交互移位序列问题是SRT一个自然的推广.这个问题可以归约为寻找一个基因组相对于另一个基因组的全部可行交互移位,即所有移位ρ满足:在一个基因组上执行ρ之后,所得基因组相对于另一个基因组的移位距离会减少.本文提出一个用来寻找全部可行交互移位的有效算法,尽管新算法的时间复杂度比穷举法改进不大,但实验结果表明,其在实际运行中表现更好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	栾峻峰	山东大学计算机科学与技术学院	12	19	3.0	3.0
2	陈超	山东大学计算机科学与技术学院	21	175	7.0	13.0