Please use this identifier to cite or link to this item:
Type: Artigo
Title: On the complexity of sorting by reversals and transpositions problems
Author: Oliveira, Andre Rodrigues
Brito, Klairton Lima
Dias, Ulisses
Dias, Zanoni
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
Subject: Rearranjo de genomas
Country: Estados Unidos
Editor: Mary Ann Liebert
Rights: Fechado
Identifier DOI: 10.1089/cmb.2019.0078
Date Issue: 2019
Appears in Collections:IC - Artigos e Outros Documentos
FT - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000468783900001.pdf298.28 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.