@techreport{TR-IC-06-01,
  number = {IC-06-01},
  author = {Cleber V. G. Mira and João Meidanis},
  title = {Sorting by Block-Interchanges and Signed Reversals},
  month = {January},
  year = {2006}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 11 pages.
    \par\selectlanguage{brazil}\textbf{Resumo}
       Uma \emph{troca de blocos} é um evento de rearranjo que
       troca duas regiões cont{\'{\i}}guas e não
       necessariamente consecutivas em um genoma, mantendo a
       orientação original de cada
       bloco. \emph{Reversões com sinal} são eventos que
       invertem e trocam a orientação dos blocos de uma
       região no genoma. Ambos os eventos são importantes para
       a análise comparativa de genomas. Por essa razão,
       nós propomos uma nova medida que consiste em encontrar uma
       seqüência m{\'{\i}}nima de trocas de bloco e
       reversões com sinal que transformem um genoma em
       outro. Para cada evento, atribuimos um peso relacionado a sua
       \emph{norma} e argumentamos que esse parâmetro é
       adequado para indicar o poder de cada evento.

       Nós apresentamos uma fórmula para a medida de rearranjo
       e um algoritmo de tempo polinomial para encontrar uma
       seqüência de trocas de blocos e reversões com sinal
       que transformem um genoma unicromossomal em outro.
    
    \par\selectlanguage{english}\textbf{Abstract}
       A  \emph{block-interchange}  is   a  rearrangement  event  that
       exchanges two, not  necessarily consecutive, contiguous regions
       in a genome, maintaining the original orientation. \emph{Signed
       reversals} are events that invert and change the orientation of
       a  region  in a  genome.  Both  events  are important  for  the
       comparative analysis of genomes.  For this reason, we propose a
       new  measure that  consists in  finding a  minimum  sequence of
       block-interchanges  and  signed  reversals  that  transforms  a
       genome into another. For each event, we assign a weight related
       to its \emph{norm} and we  argue the adequacy of this parameter
       to indicate the power of each event.
       \par
       We present a formula for the rearrangement measure and a
       polynomial time sorting algorithm for finding a sequence of
       block-interchanges and signed reversals that transforms a
       unichromosomal genome into another.
  }
}