Please use this identifier to cite or link to this item:
Type: Artigo
Title: Sorting by genome rearrangements on both gene order and intergenic sizes
Author: Brito, Klairton Lima
Jean, Geraldine
Fertin, Guillaume
Oliveira, Andre Rodrigues
Dias, Ulisses
Dias, Zanoni
Abstract: During the evolutionary process, genomes are affected by various genome rearrangements, that is, events that modify large stretches of the genetic material. In the literature, a large number of models have been proposed to estimate the number of events that occurred during evolution; most of them represent a genome as an ordered sequence of genes, and, in particular, disregard the genetic material between consecutive genes. However, recent studies showed that taking into account the genetic material between consecutive genes can enhance evolutionary distance estimations. Reversal and transposition are genome rearrangements that have been widely studied in the literature. A reversal inverts a (contiguous) segment of the genome, while a transposition swaps the positions of two consecutive segments. Genomes also undergo nonconservative events (events that alter the amount of genetic material) such as insertions and deletions, in which genetic material from intergenic regions of the genome is inserted or deleted, respectively. In this article, we study a genome rearrangement model that considers both gene order and sizes of intergenic regions. We investigate the reversal distance, and also the reversal and transposition distance between two genomes in two scenarios: with and without nonconservative events. We show that these problems are NP-hard and we present constant ratio approximation algorithms for all of them. More precisely, we provide a 4-approximation algorithm for the reversal distance, both in the conservative and nonconservative versions. For the reversal and transposition distance, we provide a 4.5-approximation algorithm, both in the conservative and nonconservative versions. We also perform experimental tests to verify the behavior of our algorithms, as well as to compare the practical and theoretical results. We finally extend our study to scenarios in which events have different costs, and we present constant ratio approximation algorithms for each scenario
Subject: Algoritmos de aproximação
Rearranjo de genomas
Country: Estados Unidos
Editor: Mary Ann Liebert
Rights: Fechado
Identifier DOI: 10.1089/cmb.2019.0293
Date Issue: 2020
Appears in Collections:IC - Artigos e Outros Documentos
FT - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000505016300002.pdf818.98 kBAdobe PDFView/Open

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