Sorting by reversals and block-interchanges with various weight assignments.
BACKGROUND
A classical problem in studying genome rearrangements is understanding the series of rearrangement events involved in transforming one genome into another in accordance with the parsimonious principle when two genomes with the same set of genes differ in gene order. The most studied event is the reversal, but an increasing number of reports have considered reversals along with other genome rearrangement events. Some recent studies have investigated the use of reversals and block-interchanges simultaneously with a weight proportion of 1:2. However, there has been less progress towards exploring additional combinations of weights.


RESULTS
In this paper, we present several approaches to examine genome rearrangement problems by considering reversals and block-interchanges together using various weight assignments. An exact algorithm for the weight proportion of 1:2 is developed, and then, its idea is extended to design approximation algorithms for other weight assignments. The results of our simulations suggest that the performance of our approximation algorithm is superior to its theoretical expectation.


CONCLUSIONS
If the weight of reversals is no more than that of block-interchanges, our algorithm provides an acceptable solution for the transformation of two permutations. Nevertheless whether there are more tractable results for studying the two events remains open.
Lin
Ying Chih
YC
Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. yclin@cse.nsysu.edu.tw
Lin
Chun-Yuan
CY
Lin
Chunhung Richard
CR
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D015321:Gene Rearrangement / Q000235:genetics*; D016678:Genome