Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Super short operations on both gene order and intergenic sizes

Texto completo
Autor(es):
Oliveira, Andre R. [1] ; Jean, Geraldine [2] ; Fertin, Guillaume [2] ; Dias, Ulisses [3] ; Dias, Zanoni [1]
Número total de Autores: 5
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Univ Nantes, UMR CNRS 6004, LS2N, Nantes - France
[3] Univ Estadual Campinas, Sch Technol, Limeira - Brazil
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: Algorithms for Molecular Biology; v. 14, n. 1 NOV 5 2019.
Citações Web of Science: 0
Resumo

Background The evolutionary distance between two genomes can be estimated by computing a minimum length sequence of operations, called genome rearrangements, that transform one genome into another. Usually, a genome is modeled as an ordered sequence of genes, and most of the studies in the genome rearrangement literature consist in shaping biological scenarios into mathematical models. For instance, allowing different genome rearrangements operations at the same time, adding constraints to these rearrangements (e.g., each rearrangement can affect at most a given number of genes), considering that a rearrangement implies a cost depending on its length rather than a unit cost, etc. Most of the works, however, have overlooked some important features inside genomes, such as the presence of sequences of nucleotides between genes, called intergenic regions. Results and conclusions In this work, we investigate the problem of computing the distance between two genomes, taking into account both gene order and intergenic sizes. The genome rearrangement operations we consider here are constrained types of reversals and transpositions, called super short reversals (SSRs) and super short transpositions (SSTs), which affect up to two (consecutive) genes. We denote by super short operations (SSOs) any SSR or SST. We show 3-approximation algorithms when the orientation of the genes is not considered when we allow SSRs, SSTs, or SSOs, and 5-approximation algorithms when considering the orientation for either SSRs or SSOs. We also show that these algorithms improve their approximation factors when the input permutation has a higher number of inversions, where the approximation factor decreases from 3 to either 2 or 1.5, and from 5 to either 3 or 2. (AU)

Processo FAPESP: 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade
Beneficiário:Anderson de Rezende Rocha
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo
Beneficiário:Sandra Eliza Fontes de Avila
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
Beneficiário:Munir Salomao Skaf
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático