Limites para distância e diâmetro em rearranjo de genomas por transposições
Abstract
Sorting by transpositions is a classic problem proposed in genome rearrangement and settled as NP-hard. The historical approach has been to study permutations candidates to be diametral. The transposition diameter is a related challenging open problem. We advance the study of both problems. We present tighter bounds for the distance of lonely permutations, we set the current lower bound for the diameter, and also show families that reach such bound. Furthermore, we propose a strategy to increase the lower bound.
References
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.
Published
2014-07-28
How to Cite
CUNHA, Luis Felipe; DE FIGUEIREDO, Celina; KOWADA, Luis Antonio.
Limites para distância e diâmetro em rearranjo de genomas por transposições. In: THESIS AND DISSERTATION CONTEST (CTD), 27. , 2014, Brasília.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 73-78.
ISSN 2763-8820.
