Your browser doesn't support javascript.
loading
A faster 1.375-approximation algorithm for sorting by transpositions.
Cunha, Luís Felipe I; Kowada, Luis Antonio B; Hausen, Rodrigo de A; de Figueiredo, Celina M H.
Afiliação
  • Cunha LF; 1 COPPE - Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro , Rio de Janeiro, Brazil .
  • Kowada LA; 2 Instituto de Computação, Universidade Federal Fluminense , Rio de Janeiro, Brazil .
  • Hausen Rde A; 3 Centro de Matemática, Computação e Cognição, Universidade Federal do ABC , São Paulo, Brazil .
  • de Figueiredo CM; 1 COPPE - Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro , Rio de Janeiro, Brazil .
J Comput Biol ; 22(11): 1044-56, 2015 Nov.
Article em En | MEDLINE | ID: mdl-26383040
Sorting by Transpositions is an NP-hard problem for which several polynomial-time approximation algorithms have been developed. Hartman and Shamir (2006) developed a 1.5-approximation [Formula: see text] algorithm, whose running time was improved to O(nlogn) by Feng and Zhu (2007) with a data structure they defined, the permutation tree. Elias and Hartman (2006) developed a 1.375-approximation O(n(2)) algorithm, and Firoz et al. (2011) claimed an improvement to the running time, from O(n(2)) to O(nlogn), by using the permutation tree. We provide counter-examples to the correctness of Firoz et al.'s strategy, showing that it is not possible to reach a component by sufficient extensions using the method proposed by them. In addition, we propose a 1.375-approximation algorithm, modifying Elias and Hartman's approach with the use of permutation trees and achieving O(nlogn) time.
Assuntos
Palavras-chave
Texto completo
Adicionar na Minha BVS
Imprimir
XML
PubMed Links
Buscar no Google

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Assunto principal: Análise de Sequência de DNA Tipo de estudo: Prognostic_studies Idioma: En Revista: J Comput Biol Assunto da revista: BIOLOGIA MOLECULAR / INFORMATICA MEDICA Ano de publicação: 2015 Tipo de documento: Article País de afiliação: Brasil País de publicação: Estados Unidos
Texto completo
Adicionar na Minha BVS
Imprimir
XML
PubMed Links
Buscar no Google

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Assunto principal: Análise de Sequência de DNA Tipo de estudo: Prognostic_studies Idioma: En Revista: J Comput Biol Assunto da revista: BIOLOGIA MOLECULAR / INFORMATICA MEDICA Ano de publicação: 2015 Tipo de documento: Article País de afiliação: Brasil País de publicação: Estados Unidos