Your browser doesn't support javascript.
loading
Reversals and transpositions distance with proportion restriction.
Brito, Klairton Lima; Alexandrino, Alexsandro Oliveira; Oliveira, Andre Rodrigues; Dias, Ulisses; Dias, Zanoni.
Afiliação
  • Brito KL; Institute of Computing, University of Campinas, 1251 Albert Einstein Ave., 13083-852 Campinas, So Paulo, Brazil.
  • Alexandrino AO; Institute of Computing, University of Campinas, 1251 Albert Einstein Ave., 13083-852 Campinas, So Paulo, Brazil.
  • Oliveira AR; Institute of Computing, University of Campinas, 1251 Albert Einstein Ave., 13083-852 Campinas, So Paulo, Brazil.
  • Dias U; School of Technology, University of Campinas, 1888 Paschoal Marmo St., 13484-332 Limeira, So Paulo, Brazil.
  • Dias Z; Institute of Computing, University of Campinas, 1251 Albert Einstein Ave., 13083-852 Campinas, So Paulo, Brazil.
J Bioinform Comput Biol ; 19(4): 2150013, 2021 08.
Article em En | MEDLINE | ID: mdl-34162319
In the field of comparative genomics, one way of comparing two genomes is through the analysis of how they distinguish themselves based on a set of mutations called rearrangement events. When considering that genomes undergo different types of rearrangements, it can be assumed that some events are more common than others. To model this assumption, one can assign different weights to different events, where common events tend to cost less than others. However, this approach, called weighted, does not guarantee that the rearrangement assumed to be the most frequent will be also the most frequently returned by proposed algorithms. To overcome this issue, we investigate a new problem where we seek the shortest sequence of rearrangement events able to transform one genome into the other, with a restriction regarding the proportion between the events returned. Here, we consider two rearrangement events: reversal, that inverts the order and the orientation of the genes inside a segment of the genome, and transposition, that moves a segment of the genome to another position. We show the complexity of this problem for any desired proportion considering scenarios where the orientation of the genes is known or unknown. We also develop an approximation algorithm with a constant approximation factor for each scenario and, in particular, we describe an improved (asymptotic) approximation algorithm for the case where the gene orientation is known. At last, we present the experimental tests comparing the proposed algorithms with others from the literature for the version of the problem without the proportion restriction.
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: Genoma / Genômica Tipo de estudo: Prognostic_studies Idioma: En Revista: J Bioinform Comput Biol Assunto da revista: BIOLOGIA / INFORMATICA MEDICA Ano de publicação: 2021 Tipo de documento: Article País de afiliação: Brasil País de publicação: Singapura
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: Genoma / Genômica Tipo de estudo: Prognostic_studies Idioma: En Revista: J Bioinform Comput Biol Assunto da revista: BIOLOGIA / INFORMATICA MEDICA Ano de publicação: 2021 Tipo de documento: Article País de afiliação: Brasil País de publicação: Singapura