title: On the family-free DCJ distance and similarity.
abstract: Structural variation in genomes can be revealed by many (dis)similarity measures. Rearrangement operations, such as the so called double-cut-and-join (DCJ), are large-scale mutations that can create complex changes and produce such variations in genomes. A basic task in comparative genomics is to find the rearrangement distance between two given genomes, i.e., the minimum number of rearragement operations that transform one given genome into another one. In a family-based setting, genes are grouped into gene families and efficient algorithms have already been presented to compute the DCJ distance between two given genomes. In this work we propose the problem of computing the DCJ distance of two given genomes without prior gene family assignment, directly using the pairwise similarities between genes. We prove that this new family-free DCJ distance problem is APX-hard and provide an integer linear program to its solution. We also study a family-free DCJ similarity and prove that its computation is NP-hard.
authors: Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Avenida Costa e Silva, s-n, Campo Grande, 79070-900 MS Brazil ; Technische Fakultät and CeBiTec, Universität Bielefeld, Universitätsstr. 25, Bielefeld, 33615 Germany.
authors: Fábio V
authors: FV
authors: Martinez
authors: Technische Fakultät and CeBiTec, Universität Bielefeld, Universitätsstr. 25, Bielefeld, 33615 Germany.
authors: Pedro
authors: P
authors: Feijão
authors: Inmetro - Instituto Nacional de Metrologia, Qualidade e Tecnologia, Av. Nossa Senhora das Graças, 50, Duque de Caxias, 25250-020 RJ Brazil.
authors: Marília Dv
authors: MD
authors: Braga
authors: Technische Fakultät and CeBiTec, Universität Bielefeld, Universitätsstr. 25, Bielefeld, 33615 Germany.
authors: Jens
authors: J
authors: Stoye
keywords: DCJ; Family-free genome comparison; Genome rearrangement