Limites para distância e diâmetro em rearranjo de genomas por transposições
Resumo
Ordenação por tranposições é um clássico problema em rearranjo de genomas, provado ser NP-difícil. Historicamente tem sido considerado o estudo de permutações candidatas a serem diametrais. O diâmetro de transposição é assim relacionado ao problema de ordenação, em aberto, bastante desafiador. Avançamos em ambos problemas. Apresentamos limites justos para distância de famílias de permutações solitárias, estabelecemos o limite inferior para o diâmetro, e apresentamos famílias que por uniões de permutações solitárias atingem este limite. Além disso apresentamos uma estratégia que possivelmente aumentará o limite inferior.
Referências
Bafna, V. e Pevzner, P. A. (1998). Sorting by transpositions. SIAM J. Discrete Math., 11(2):224–240.
Bóna, M. (2012). Combinatorics of Permutations. The CRC Press.
Bulteau, L., Fertin, G. e Rusu, I. (2012). Sorting by transpositions is difficult. SIAM J. Discrete Math., 26(3):1148–1180.
Christie, D. A. (1999). Genome Rearrangement Problems. Phd. thesis, University of Glasgow, UK.
Cunha, L. F. I. e Kowada, L. A. B. (2010). Upper bounds and exact values on transposition distance of permutations. Mat. Contemp., 39:77–84.
Cunha, L. F. I., Kowada, L. A. B., Hausen, R. A. e de Figueiredo, C. M. H. (2012). Transposition diameter and lonely permutations. In Advances in Bioinformatics and Computational Biology, pages 1–12.
LNBI, Springer-Verlag. Cunha, L. F. I., Kowada, L. A. B., Hausen, R. A. e de Figueiredo, C. M. H. (2013). Advancing the transposition distance and diameter through lonely permutations. SIAM J. Discrete Math., 27(4):1682–1709.
Elias, I. e Hartman, T. (2006). A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans. Comput. Biol. Bioinformatics, 3(4):369–379.
Eriksson, H., Eriksson, K., Karlander, J., Svensson, L. J. e Wastlund, J. (2001). Sorting a bridge hand. Discrete Math., 241(1-3):289–300.
Lu, L. e Yang, Y. (2010). A lower bound on the transposition diameter. SIAM J. Discrete Math., 24(4):1242–1249.
Bóna, M. (2012). Combinatorics of Permutations. The CRC Press.
Bulteau, L., Fertin, G. e Rusu, I. (2012). Sorting by transpositions is difficult. SIAM J. Discrete Math., 26(3):1148–1180.
Christie, D. A. (1999). Genome Rearrangement Problems. Phd. thesis, University of Glasgow, UK.
Cunha, L. F. I. e Kowada, L. A. B. (2010). Upper bounds and exact values on transposition distance of permutations. Mat. Contemp., 39:77–84.
Cunha, L. F. I., Kowada, L. A. B., Hausen, R. A. e de Figueiredo, C. M. H. (2012). Transposition diameter and lonely permutations. In Advances in Bioinformatics and Computational Biology, pages 1–12.
LNBI, Springer-Verlag. Cunha, L. F. I., Kowada, L. A. B., Hausen, R. A. e de Figueiredo, C. M. H. (2013). Advancing the transposition distance and diameter through lonely permutations. SIAM J. Discrete Math., 27(4):1682–1709.
Elias, I. e Hartman, T. (2006). A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans. Comput. Biol. Bioinformatics, 3(4):369–379.
Eriksson, H., Eriksson, K., Karlander, J., Svensson, L. J. e Wastlund, J. (2001). Sorting a bridge hand. Discrete Math., 241(1-3):289–300.
Lu, L. e Yang, Y. (2010). A lower bound on the transposition diameter. SIAM J. Discrete Math., 24(4):1242–1249.
Publicado
28/07/2014
Como Citar
CUNHA, Luis Felipe; DE FIGUEIREDO, Celina; KOWADA, Luis Antonio.
Limites para distância e diâmetro em rearranjo de genomas por transposições. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 27. , 2014, Brasília.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 73-78.
ISSN 2763-8820.
