基于第一降序小队翻转排序算法  

An Approximate Algorithm Of Sorting Reversal Based On First Descending Strip

作　　者：刘声田[1] 王娟[2] 

机构地区：[1]山东广播电视大学,山东济南250014 [2]中共烟台市委党校,山东烟台264000

出　　处：《山东电大学报》2006年第4期68-69,共2页Journal of Shandong TV University

摘　　要：计算不同基因序列的演化距离问题可以转换为寻找两个排列间的翻转距离问题,对于大部分实例来说,最小排序翻转序列是存在的。在探索基因重排空间问题上,获取最小翻转距离非常有意义。引入了两个引理并证明了引理,然后描述了FDSR算法,最后分析了算法的效率并得出了结论。The problem of estimation evolutionary distance from differences in gene order has been distilled to the problem of finding the reversal distance between two signed permutations.For most problem instances,many minimum sequences of sorting reversals exist,and it is very important to explore the space of genome rearrangements.In this paper,we begin by introducing two lemmas and proving them;then we describe the approximate algorithm named FDSR;finally,we analyze the algorithm and form a conclusion.

关 键 词：基因组重排 翻转排序 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]