Metraipolis › archive › dc_b8ddbfaf3154
NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance — arXiv:2609.18397
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18397
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T17:09:19.662Z
- SHA-256 of the archived text
0f6f4fd405f0668f7ce5b64db20dbe812eaa4cab2594b6fe907d4e0fbf9c8cdd- Stable URL of this page
https://metraipolis.com/documento/dc_b8ddbfaf3154
How to cite
NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance — arXiv:2609.18397 — arXiv (en), https://arxiv.org/abs/2609.18397 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b8ddbfaf3154 (Metraipolis archive dc_b8ddbfaf3154, sha256 0f6f4fd405f0668f7ce5b64db20dbe812eaa4cab2594b6fe907d4e0fbf9c8cdd)
BibTeX
@misc{dcb8ddbfaf3154,
title = {NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance — arXiv:2609.18397},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18397},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b8ddbfaf3154; sha256 0f6f4fd405f0668f7ce5b64db20dbe812eaa4cab2594b6fe907d4e0fbf9c8cdd},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18397. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.18397 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.262Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).