摘要
计算不同基因序列的演化距离问题可以转换为寻找两个排列间的翻转距离问题,对于大部分实例来说,最小排序翻转序列是存在的。在探索基因重排空间问题上,获取最小翻转距离非常有意义。引入了两个引理并证明了引理,然后描述了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.
出处
《山东电大学报》
2006年第4期68-69,共2页
Journal of Shandong TV University
关键词
基因组重排
翻转排序
genome rearrangement,sorting by reversals