0

一些简单的生物体有一个环状 DNA 分子作为基因组，该分子没有起点也没有终点。这些圆形基因组可以被可视化为沿着圆的周边书写的整数序列。

置换的交换排序是通过交换相邻元素转换为恒等置换。例如， 3142 ！1342！1324！1234 是排列 3124 的三步交换排序。

现在的问题是：设计一种交换排序算法，使用最小交换次数对循环排列进行排序。

4

1 回答 1

1

不仅仅是简单的有机体；mtDNA 也是环状的。

有许多算法可以解决您的问题——允许不同的操作来解释距离（插入删除事件、复制、反转等）。

两个主要的算法是，

  • 断点距离（参见：M. Blanchette、G. Bourque 和 D. Sankoff。 基因组信息学，关于断点系统发育的章节，第 25-34 页。环球学院出版社）

  • Double-Cut and Join（参见：S. Yancopoulos、O. Attie 和 R. Friedberg。通过易位、倒位和块交换对基因组排列进行有效排序）

您可能想查看 MGR 并避免自己实现这些算法。我使用的软件包包括 GRAPPA 和 MGR，经过数月的努力修复了许多错误。

于 2013-05-09T21:07:43.547 回答