Please use this identifier to cite or link to this item:
Type: Artigo
Title: Sorting by weighted reversals and transpositions
Author: Oliveira, Andre Rodrigues
Brito, Klairton Lima
Dias, Zanoni
Dias, Ulisses
Abstract: Genome rearrangements are global mutations that change large stretches of DNA sequence throughout genomes. They are rare but accumulate during the evolutionary process leading to organisms with similar genetic material in different places and orientations within the genome. Sorting by Genome Rearrangements problems seek for minimum-length sequences of rearrangements that transform one genome into the other. These problems accept alternative versions that assign weights for each event, and the goal is to find a minimum-weight sequence. We study the Sorting by Weighted Reversals and Transpositions problem on signed permutations. In this study, we use weight 2 for reversals and 3 for transpositions and consider theoretical and practical aspects in our analysis. We present two algorithms with approximation factors of 5/3 and 3/2. We also developed a generic approximation algorithm to deal with different weights for reversals and transpositions, and we show the approximation factor reached in each scenario
Subject: Algoritmos de aproximação
Rearranjo de genomas
Country: Estados Unidos
Editor: Mary Ann Liebert
Rights: Fechado
Identifier DOI: 10.1089/cmb.2018.0257
Date Issue: 2019
Appears in Collections:IC - Artigos e Outros Documentos
FT - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000467484600002.pdf819.15 kBAdobe PDFView/Open

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