Article ID Journal Published Year Pages File Type
430764 Journal of Computer and System Sciences 2008 31 Pages PDF
Abstract

We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(ℓ)=ℓα for all α⩾0, where ℓ 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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics