Your browser doesn't support javascript.
loading
Sorting by Genome Rearrangements on Both Gene Order and Intergenic Sizes.
Brito, Klairton Lima; Jean, Géraldine; Fertin, Guillaume; Oliveira, Andre Rodrigues; Dias, Ulisses; Dias, Zanoni.
Afiliação
  • Brito KL; Institute of Computing, University of Campinas, Campinas, Brazil.
  • Jean G; LS2N UMR CNRS 6004, Université de Nantes, Nantes, France.
  • Fertin G; LS2N UMR CNRS 6004, Université de Nantes, Nantes, France.
  • Oliveira AR; Institute of Computing, University of Campinas, Campinas, Brazil.
  • Dias U; School of Technology, University of Campinas, Limeira, Brazil.
  • Dias Z; Institute of Computing, University of Campinas, Campinas, Brazil.
J Comput Biol ; 27(2): 156-174, 2020 Feb.
Article em En | MEDLINE | ID: mdl-31891533
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.
Palavras-chave

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Idioma: En Revista: J Comput Biol Assunto da revista: BIOLOGIA MOLECULAR / INFORMATICA MEDICA Ano de publicação: 2020 Tipo de documento: Article País de afiliação: Brasil País de publicação: Estados Unidos

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Idioma: En Revista: J Comput Biol Assunto da revista: BIOLOGIA MOLECULAR / INFORMATICA MEDICA Ano de publicação: 2020 Tipo de documento: Article País de afiliação: Brasil País de publicação: Estados Unidos