arXiv preprint ·
NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A quantitative tree-likeness bound from average hyperbolicity
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Universal set families for maximization of nonnegative submodular and XOS functions
Serial-batch scheduling to minimise the total weighted late work
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.