使用交換排序圓形置換

一些簡單的生物體具有環狀DNA分子作爲基因組，其中分子沒有開始和結束。這些循環基因組可以被看作是沿着圓周寫的一系列整數。使用交換排序圓形置換

排列的交換排序是通過交換相鄰元素到身份排列的轉換。例如，3142！ 1342！ 1324！ 1234是排列3124的三步交換排序。

現在的問題是：設計一個交換排序算法，該算法使用交換的最小數量來排序圓形排列。

2013-05-09 behnam rasti

[使用交換排序圓形排列]的可能重複（http://stackoverflow.com/questions/16436170/sorting-a-circular-permutation-using-swap）;請不要製造重複的問題;相反，改善原來的文章，如果它沒有得到你想要的答案 – 2013-05-09 08:27:02

不幸的是，這是一個體面的問題（這確實需要一些工作），但前一個線程是封閉的，相當污染。 – nlucaroni 2013-05-09 16:05:25

不僅僅是簡單的生物;線粒體DNA也是循環的。

有許多算法可以解決您的問題 - 允許考慮距離（indel事件，重複，倒位等）的不同操作。

這種情況的兩個主要的算法是，

斷點距離（參見：M.布蘭切特，G.布爾克和D. Sankoff 基因組信息，在斷點系統發育章，第25頁。-34 通用科學院出版社）
雙切和加入（參見：S. Yancopoulos，O. Attie和R.弗裏德伯格高效排序易位基因組排列，inversi上塊交換）

你可能想看看MGR和避免實施這些算法自己。 The software package我的工作包括GRAPPA和MGR以及數月努力的許多錯誤修復。

來源

2013-05-09 21:07:43 nlucaroni

tanx很多哥們 – 2013-05-09 21:29:13

使用交換排序圓形置換

回答

相關問題