title: Approximating the DCJ distance of balanced genomes in linear time.
abstract: BACKGROUND
  Rearrangements are large-scale mutations in genomes, responsible for complex changes and structural variations. Most rearrangements that modify the organization of a genome can be represented by the double cut and join (DCJ) operation. Given two balanced genomes, i.e., two genomes that have exactly the same number of occurrences of each gene in each genome, we are interested in the problem of computing the rearrangement distance between them, i.e., finding the minimum number of DCJ operations that transform one genome into the other. This problem is known to be NP-hard.
  
  
  RESULTS
  We propose a linear time approximation algorithm with approximation factorO(k) for the DCJ distance problem, wherekis the maximum number of occurrences of any gene in the input genomes. Our algorithm works for linear and circular unichromosomal balanced genomes and uses as an intermediate step anO(k)-approximation for the minimum common string partition problem, which is closely related to the DCJ distance problem.
  
  
  CONCLUSIONS
  Experiments on simulated data sets show that our approximation algorithm is very competitive both in efficiency and in quality of the solutions.
authors.affiliation: Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS Brazil.
authors.forename: Diego P
authors.initials: DP
authors.lastname: Rubert
authors.affiliation: Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany.
authors.forename: Pedro
authors.initials: P
authors.lastname: Feijão
authors.affiliation: Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany.
authors.forename: Marília Dias Vieira
authors.initials: MDV
authors.lastname: Braga
authors.affiliation: Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany.
authors.forename: Jens
authors.identifier: 0000-0002-4656-7155
authors.initials: J
authors.lastname: Stoye
authors.affiliation: Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS Brazil.
authors.forename: Fábio Henrique Viduani
authors.initials: FHV
authors.lastname: Martinez
keywords: Approximation algorithms; Comparative genomics; Double cut and join (DCJ); Genome rearrangements