Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

On the Complexity of Sorting by Reversals and Transpositions Problems

Full text
Author(s):
Oliveira, Andre Rodrigues [1] ; Brito, Klairton Lima [1] ; Dias, Ulisses [2] ; Dias, Zanoni [1]
Total Authors: 4
Affiliation:
[1] Univ Estadual Campinas, Inst Comp, Ave Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil
[2] Univ Estadual Campinas, Sch Technol, Limeira - Brazil
Total Affiliations: 2
Document type: Journal article
Source: JOURNAL OF COMPUTATIONAL BIOLOGY; v. 26, n. 11, p. 1223-1229, NOV 1 2019.
Web of Science Citations: 1
Abstract

In comparative genomics, rearrangements are mutations that affect a stretch of DNA sequences. Reversals and transpositions are well-known rearrangements, and each has a vast literature. The reversal and transposition distance, that is, the minimum number of reversals and transpositions needed to transform one genome into another is a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations was proposed >20 years ago and received the name of sorting by reversals and transpositions problem. It has been the focus of a number of studies, but the computational complexity has remained open until now. We hereby solve this question and prove that it is NP-hard no matter whether genomes are represented by signed or unsigned permutations. In addition, we prove that a usual generalization of this problem, which assigns weights w(rho) for reversals and w(tau) for transpositions, is also NP-hard as long as w(tau)/w(rho) <= 1.5 for both signed and unsigned permutations. (AU)

FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
Grantee:Munir Salomao Skaf
Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 17/16246-0 - Sensitive media analysis through deep learning architectures
Grantee:Sandra Eliza Fontes de Avila
Support Opportunities: Regular Research Grants
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events
Grantee:Anderson de Rezende Rocha
Support Opportunities: Research Projects - Thematic Grants