Genome translocation distance proven hard and solvable with fixed parameter
NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance
Data Structures and Algorithms
Summary
This paper studies how we can measure the differences between groups of DNA strings by swapping parts between them, mimicking biological events called translocations. The researchers show that figuring out the smallest number of these swaps needed to get from one set of DNA strings to another is a very hard problem in general. However, when the target is just one DNA string, they provide an efficient algorithm that works well if the target string is not too long. This helps understand the complexity of comparing DNA rearrangements and offers a practical way to solve a special case.
What this means in practice
- •For bioinformatics software developers: Design tools to compute genome rearrangement distances efficiently when comparing a single target chromosome.
- •For algorithm designers: Avoid expecting efficient solutions for general translocation distance problems due to proven NP-hardness.
A theory result. No direct application yet.
Authors
Maria Constantin, Adrian Miclăuş, Alexandru Popa
Abstract
In this paper we study the genome rearrangements done by translocation events. Genome rearrangements were used to measure evolutionary distance between organisms since 1936 (Dobzhansky and Sturtevant). The chromosomes are represented as strings of DNA and the \emph{translocation operation} is defined as the exchange of prefixes between two strings. This operation results in the creation of two new strings (chromosomes) that can then be utilized in subsequent translocations. A translocation is referred to as \emph{contiguous} if the new strings are produced in a single copy, so each of them can be used in only one subsequent operation. When the words produced by a translocation operation are considered to have an infinite number of copies, the translocation is referred to as \emph{non-contiguous}. If the exchanged prefixes are of equal length, the translocation is called \emph{uniform}. Otherwise, the translocation is termed \emph{non-uniform}. The \emph{translocation distance} between two sets of strings, termed the input set and the target set, represents the minimum number of translocations necessary to obtain all the strings in the target set via translocation operations. We prove that both the non-uniform contiguous and the non-uniform non-contiguous translocation distance problems are NP-hard over arbitrary finite alphabets, where the alphabet is part of the input. For the case in which the target set consists of a single string, we give a fixed-parameter tractable algorithm parameterized by the length of the target string.