Improved bounds on sorting by length-weighted reversals
We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(l) = l(alpha) for all alpha >= 0, where l is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics. (c) 2007 Elsevier Inc. All rights reserved.
sorting by reversals potential functions dynamic programming soiling 0/1 sequences by reversals modeling genome rearrangements