@techreport{TR-IC-00-23,
number = {IC-00-23},
author = {J. Meidanis and M. E. M. T. Walter and Z. Dias},
title = {Reversal Distance of Signed Circular Chromosomes},
month = {December},
year = {2000},
institution = {Institute of Computing, University of Campinas},
note = {In English, 22 pages.
\par\selectlanguage{english}\textbf{Abstract}
We study the problem of comparing two circular chromosomes,
evolved from a common ancestor by reversals, given the order of
the corresponding genes and their orientations. Determining the
minimum number of reversals between the chromosomes is equivalent
to looking for the minimum number of reversals that transform a
circular sequence of signed integer numbers, defined in an
appropriate manner, into another; where a reversal acts on a
subsequence, reversing its order and flipping the signs. We
carefully formalize the concepts of circular chromosome and
circular reversal, and show that this problem is essentially
equivalent to the analogous problem on linear chromosomes. As a
consequence we derive polynomial time algorithms based on this
observation. We also compute the reversal diameter for signed
chromosomes, both linear and circular.
}
}