| Texto completo | |
| Autor(es): |
Santos Miranda, Guilherme Henrique
;
Lintzmayer, Carla Negri
;
Dias, Zanoni
;
Jansson, J
;
MartinVide, C
;
VegaRodriguez, MA
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018); v. 10849, p. 12-pg., 2018-01-01. |
| Resumo | |
Estimating the evolutionary distance between genomes of two organisms is a challenging task for Computational Biology. One of the most well-accepted ways to do this is to consider the size of the smallest sequence of rearrangement events required to transform one genome into another, characterizing the rearrangement distance problem. Computationally, genomes can be represented as permutations of integers and, with this, the problem can be reduced to transforming a permutation into the identity with the minimum number of operations (sorting the permutation). These operations are given by a rearrangement model and they affect segments of a genome in different ways. Among the most common models are those that allow only reversals, only transpositions, or both of them. In this paper we study sorting permutations when a restriction of biological relevance is added: the size of the rearrangements should be at most a given value lambda. Some results are known for lambda = 2 and lambda = 3 but, to the best of our knowledge, there are no results for lambda > 3. We consider rearrangement models that allow reversals and/or transpositions for sorting unsigned permutations given any value of lambda. We present approximation algorithms for 3 such problems, where the approximation factors depend on lambda and/or on the size of the permutations. (AU) | |
| Processo FAPESP: | 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais |
| Beneficiário: | Munir Salomao Skaf |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |
| 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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| 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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções |
| Beneficiário: | Carla Negri Lintzmayer |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |