TY  - JOUR
AB  - 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.
DA  - 2015
DO  - 10.1186/s13015-015-0041-9
KW  - Family-free genome comparison
KW  - Genome rearrangement
KW  - DCJ
LA  - eng
IS  - 1
PY  - 2015
SN  - 1748-7188
T2  - Algorithms for Molecular Biology
TI  - On the family-free DCJ distance and similarity
UR  - https://nbn-resolving.org/urn:nbn:de:0070-pub-27263666
Y2  - 2024-11-22T01:37:57
ER  -