Ordenação de Permutações com Sinais por Reversões e Transposições
Resumo
Determinar uma sequencia de rearranjos de genomas capaz de transformar um genoma em outro pode ser bastante util na genomica comparativa. Dependendo do cenario em que nos deparamos as características buscadas para essa sequencia de rearranjos de genomas podem ser diferentes. Nessa dissertacao, trabalhamos com genomas em que a orientacao dos genes e conhecida e consideramos os eventos de rearranjo de genomas de reversao e transposicao. Abordamos o problema classico no qual ambos os eventos afetam o genoma com a mesma frequência. Alem disso, investigamos uma variacao do problema na qual cada tipo de evento ocorre com uma frequencia diferente.
Palavras-chave:
Rearranjo de genomas, heurísticas, algoritmos de aproximação
Referências
Bader, D. A., Moret, B. M. E., and Yan, M. (2001). A Linear-Time Algorithm for Com- puting Inversion Distance Between Signed Permutations with an Experimental Study. Journal ofComputational Biology, 8:483–491.
Bader, M., Abouelhoda, M. I., and Ohlebusch, E. (2008). A Fast Algorithm for the Mul- tiple Genome Rearrangement Problem with Weighted Reversals and Transpositions. BMC Bioinformatics, 9(1):1–13.
Bader, M. and Ohlebusch, E. (2007). Sorting by Weighted Reversals, Transpositions, and Inverted Transpositions. Journal ofComputational Biology, 14(5):615–636.
Bafna, V. and Pevzner, P. A. (1998). Sorting by Transpositions. SIAM Journal on Discrete Mathematics, 11(2):224–240.
Bergeron, A. (2005). AVery Elementary Presentation of the Hannenhalli-Pevzner Theory. Discrete Applied Mathematics, 146(2):134–145.
Berman, P., Hannenhalli, S., and Karpinski, M. (2002). 1.375-Approximation Algorithm for Sorting by Reversals. In Proceedings ofthe 10th Annual European Symposium on Algorithms (ESA’2002), volume 2461 of Lecture Notes in Computer Science, pages 200–210. Berlin/Heidelberg, Germany.
Blanchette, M., Kunisawa, T., and Sankoff, D. (1996). Parametric Genome Rearrange- ment. Gene, 172(1):GC11–GC17.
Brito, K. L., Oliveira, A. R., Dias, U., and Dias, Z. (2018). Heuristics for the Sorting Sig- ned Permutations by Reversals and Transpositions Problem. In Algorithms for Com- putational Biology, volume 10849, pages 65–75. Heidelberg, Germany.
Bulteau, L., Fertin, G., and Rusu, I. (2012). Sorting by Transpositions is Difficult. SIAM Journal on Computing, 26(3):1148–1180.
Caprara, A. (1999). Sorting Permutations by Reversals and Eulerian Cycle Decompositi- ons. SIAM Journal on Discrete Mathematics, 12(1):91–110.
de Lima Brito, K. (2018). Sorting Signed Permutations by Reversals and Transpositions. Master’s thesis, Institute of Computing, University of Campinas, Brazil. In Portuguese.
Dias, U., Galv˜ao, G. R., Lintzmayer, C. N., and Dias, Z. (2014). A General Heuristic for Genome Rearrangement Problems. Journal of Bioinformatics and Computational Biology, 12(3):26.
Dias, U. M. (2012). Problemas de Comparacao de Genomas. PhD thesis, Institute of Computing, University of Campinas. In Portuguese.
Elias, I. and Hartman, T. (2006). A 1.375-Approximation Algorithm for Sorting by Trans- positions. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):369–379.
Eriksen, N. (2001). Combinatorics ofGenome Rearrangements and Phylogeny. Tekno- logie licentiat thesis, Kungliga Tekniska H¨ogskolan, Stockholm.
Eriksen, N. (2002). (1+?)-Approximation of Sorting by Reversals and Transpositions. Theoretical Computer Science, 289(1):517–529.
Fertin, G., Labarre, A., Rusu, I., Tannier, E.,´ and Vialette, S. (2009). Combinatorics of
Genome Rearrangements. Computational Molecular Biology. The MIT Press, London, England.
Hannenhalli, S. and Pevzner, P. A. (1999). Transforming Cabbage into Turnip: Polyno- mial Algorithm for Sorting Signed Permutations by Reversals. Journal of the ACM, 46(1):1–27.
Oliveira, A. R., Brito, K. L., Dias, Z., and Dias, U. (2018). Sorting byWeighted Reversals and Transpositions. In Advances in Bioinformatics and Computational Biology, pages 38–49. Heidelberg, Germany.
Oliveira, A. R., Brito, K. L., Dias, Z., and Dias, U. (2019). Sorting byWeighted Reversals and Transpositions. Journal ofComputational Biology, pages 1–12.
Rahman, A., Shatabda, S., and Hasan, M. (2008). An Approximation Algorithm for Sorting by Reversals and Transpositions. Journal of Discrete Algorithms, 6(3):449– 457.
Walter, M. E. M. T., Dias, Z., and Meidanis, J. (1998). Reversal and Transposition Dis- tance of Linear Chromosomes. In Proceedings ofthe 5th International Symposium on String Processing and Information Retrieval (SPIRE’1998), pages 96–102, Los Ala- mitos, CA, USA.
Yancopoulos, S., Attie, O., and Friedberg, R. (2005). Efficient Sorting of Genomic Permutations by Translocation, Inversion and Block Interchange. Bioinformatics, 21(16):3340–3346.
Bader, M., Abouelhoda, M. I., and Ohlebusch, E. (2008). A Fast Algorithm for the Mul- tiple Genome Rearrangement Problem with Weighted Reversals and Transpositions. BMC Bioinformatics, 9(1):1–13.
Bader, M. and Ohlebusch, E. (2007). Sorting by Weighted Reversals, Transpositions, and Inverted Transpositions. Journal ofComputational Biology, 14(5):615–636.
Bafna, V. and Pevzner, P. A. (1998). Sorting by Transpositions. SIAM Journal on Discrete Mathematics, 11(2):224–240.
Bergeron, A. (2005). AVery Elementary Presentation of the Hannenhalli-Pevzner Theory. Discrete Applied Mathematics, 146(2):134–145.
Berman, P., Hannenhalli, S., and Karpinski, M. (2002). 1.375-Approximation Algorithm for Sorting by Reversals. In Proceedings ofthe 10th Annual European Symposium on Algorithms (ESA’2002), volume 2461 of Lecture Notes in Computer Science, pages 200–210. Berlin/Heidelberg, Germany.
Blanchette, M., Kunisawa, T., and Sankoff, D. (1996). Parametric Genome Rearrange- ment. Gene, 172(1):GC11–GC17.
Brito, K. L., Oliveira, A. R., Dias, U., and Dias, Z. (2018). Heuristics for the Sorting Sig- ned Permutations by Reversals and Transpositions Problem. In Algorithms for Com- putational Biology, volume 10849, pages 65–75. Heidelberg, Germany.
Bulteau, L., Fertin, G., and Rusu, I. (2012). Sorting by Transpositions is Difficult. SIAM Journal on Computing, 26(3):1148–1180.
Caprara, A. (1999). Sorting Permutations by Reversals and Eulerian Cycle Decompositi- ons. SIAM Journal on Discrete Mathematics, 12(1):91–110.
de Lima Brito, K. (2018). Sorting Signed Permutations by Reversals and Transpositions. Master’s thesis, Institute of Computing, University of Campinas, Brazil. In Portuguese.
Dias, U., Galv˜ao, G. R., Lintzmayer, C. N., and Dias, Z. (2014). A General Heuristic for Genome Rearrangement Problems. Journal of Bioinformatics and Computational Biology, 12(3):26.
Dias, U. M. (2012). Problemas de Comparacao de Genomas. PhD thesis, Institute of Computing, University of Campinas. In Portuguese.
Elias, I. and Hartman, T. (2006). A 1.375-Approximation Algorithm for Sorting by Trans- positions. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):369–379.
Eriksen, N. (2001). Combinatorics ofGenome Rearrangements and Phylogeny. Tekno- logie licentiat thesis, Kungliga Tekniska H¨ogskolan, Stockholm.
Eriksen, N. (2002). (1+?)-Approximation of Sorting by Reversals and Transpositions. Theoretical Computer Science, 289(1):517–529.
Fertin, G., Labarre, A., Rusu, I., Tannier, E.,´ and Vialette, S. (2009). Combinatorics of
Genome Rearrangements. Computational Molecular Biology. The MIT Press, London, England.
Hannenhalli, S. and Pevzner, P. A. (1999). Transforming Cabbage into Turnip: Polyno- mial Algorithm for Sorting Signed Permutations by Reversals. Journal of the ACM, 46(1):1–27.
Oliveira, A. R., Brito, K. L., Dias, Z., and Dias, U. (2018). Sorting byWeighted Reversals and Transpositions. In Advances in Bioinformatics and Computational Biology, pages 38–49. Heidelberg, Germany.
Oliveira, A. R., Brito, K. L., Dias, Z., and Dias, U. (2019). Sorting byWeighted Reversals and Transpositions. Journal ofComputational Biology, pages 1–12.
Rahman, A., Shatabda, S., and Hasan, M. (2008). An Approximation Algorithm for Sorting by Reversals and Transpositions. Journal of Discrete Algorithms, 6(3):449– 457.
Walter, M. E. M. T., Dias, Z., and Meidanis, J. (1998). Reversal and Transposition Dis- tance of Linear Chromosomes. In Proceedings ofthe 5th International Symposium on String Processing and Information Retrieval (SPIRE’1998), pages 96–102, Los Ala- mitos, CA, USA.
Yancopoulos, S., Attie, O., and Friedberg, R. (2005). Efficient Sorting of Genomic Permutations by Translocation, Inversion and Block Interchange. Bioinformatics, 21(16):3340–3346.
Publicado
26/06/2019
Como Citar
BRITO, Klairton de Lima; DIAS, Zanoni.
Ordenação de Permutações com Sinais por Reversões e Transposições. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 32. , 2019, Belém.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2019.6337.
