Uma Ferramenta de Auditoria para Algoritmos de Rearranjo de Genomas
Resumo
Este artigo apresenta os resultados da investigação de algoritmos de rearranjo de genomas, que possuem aplicações na estimação da distância evolutiva entre espécies. A grande maioria desses algoritmos são aproximados, por isso nós desenvolvemos uma ferramenta para avaliar suas respostas. Implementamos e avaliamos 16 algoritmos de rearranjo de genomas aproximados utilizando esta ferramenta. Como resultado, mostramos que os fatores de aproximação de alguns desses algoritmos são justos, contradizendo algumas hipóteses levantadas na literatura, e conjecturamos que o fator de aproximação de alguns outros também são.Referências
Benoît-Gagné, M. and Hamel, S. (2007). A new and faster method of sorting by transpositions. In Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching, volume 4580 of LNCS, pages 131–141, London, ON, Canada. SpringerVerlag.
Dias, Z. and Meidanis, J. (2002). Sorting by prefix transpositions. In Proceedings of the 9th International Symposium on String Processing and Information Retrieval, volume 2476 of LNCS, pages 65–76, Lisbon, Portugal. Springer-Verlag.
Fischer, J. and Ginzinger, S. W. (2005). A 2-approximation algorithm for sorting by prefix reversals. In Proceedings of the 13th Annual European Symposium on Algorithms, volume 3669 of LNCS, pages 415–425, Mallorca, Spain. Springer-Verlag.
21 Galvão, G. R. and Dias, Z. (2011a). Computing rearrangement distace of every permutation in the symmetric group. In Proceedings of the 26th ACM Symposium on Applied Computing – Conference Track on Bioinformatics and Computational Systems Biology, pages 106–107, Taichung, Taiwan. ACM Press.
Galvão, G. R. and Dias, Z. (2011b). A flexible framework for computing rearrangement distance of every permutation in the symmetric group. In Proceedings of the 6th Brazilian Symposium on Bioinformatics, pages 33–40, Brasília, Brazil.
Galvão, G. R. and Dias, Z. (2011c). On the distribution of rearrangement distances. In Proceedings of the 6th Brazilian Symposium on Bioinformatics, pages 41–48, Brasília, Brazil.
Galvão, G. R. and Dias, Z. (2011d). On the performance of sorting by transpositions without using cycle graph. In Proceedings of the 6th Brazilian Symposium on Bioinformatics, pages 69–72, Brasília, Brazil.
Galvão, G. R. and Dias, Z. (2012a). GRAAu: Genome Rearrangement Algorithm Auditor. In Proceedings of the 4th International Conference on Bioinformatics and Computational Biology, pages 97–101, Las Vegas, NV, USA. Curran Associates, Inc.
Galvão, G. R. and Dias, Z. (2012b). On the approximation ratio for sorting by short swaps. In Proceedings of the 7th Brazilian Symposium on Bioinformatics, pages 120–125, Campo Grande, MS, Brazil.
Galvão, G. R. and Dias, Z. (2012c). On the approximation ratio of algorithms for sorting by transpositions without using cycle graphs. In Proceedings of the 7th Brazilian Symposium on Bioinformatics, volume 7049 of LNCS, pages 25–36, Campo Grande, MS, Brazil. Springer-Verlag.
Galvão, G. R. and Dias, Z. (2012d). On the performance of sorting permutations by prefix operations. In Proceedings of the 4th International Conference on Bioinformatics and Computational Biology, pages 102–107, Las Vegas, NV, USA. Curran Associates, Inc.
Grusea, S. and Labarre, A. (2011). The distribution of cycles in breakpoint graphs of signed permutations. CoRR, abs/1104.3353.
Kececioglu, J. D. and Sankoff, D. (1995). Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica, 13(1-2):80–110.
Labarre, A. (2012). Lower bounding edit distances between permutations. CoRR, abs/1201.0365.
Walter, M. E. M. T., Dias, Z., and Meidanis, J. (1998). Reversal and transposition distance of linear chromosomes. In Proceedings of the 5th International Symposium on String Processing and Information Retrieval, pages 96–102, Santa Cruz, Bolivia. IEEE Computer Society.
Walter, M. E. M. T., Dias, Z., and Meidanis, J. (2000). A new approach for approximating the transposition distance. In Proceedings of the 7th International Symposium on String Processing Information Retrieval, pages 199–208, Washington, DC, USA. IEEE Computer Society.
Dias, Z. and Meidanis, J. (2002). Sorting by prefix transpositions. In Proceedings of the 9th International Symposium on String Processing and Information Retrieval, volume 2476 of LNCS, pages 65–76, Lisbon, Portugal. Springer-Verlag.
Fischer, J. and Ginzinger, S. W. (2005). A 2-approximation algorithm for sorting by prefix reversals. In Proceedings of the 13th Annual European Symposium on Algorithms, volume 3669 of LNCS, pages 415–425, Mallorca, Spain. Springer-Verlag.
21 Galvão, G. R. and Dias, Z. (2011a). Computing rearrangement distace of every permutation in the symmetric group. In Proceedings of the 26th ACM Symposium on Applied Computing – Conference Track on Bioinformatics and Computational Systems Biology, pages 106–107, Taichung, Taiwan. ACM Press.
Galvão, G. R. and Dias, Z. (2011b). A flexible framework for computing rearrangement distance of every permutation in the symmetric group. In Proceedings of the 6th Brazilian Symposium on Bioinformatics, pages 33–40, Brasília, Brazil.
Galvão, G. R. and Dias, Z. (2011c). On the distribution of rearrangement distances. In Proceedings of the 6th Brazilian Symposium on Bioinformatics, pages 41–48, Brasília, Brazil.
Galvão, G. R. and Dias, Z. (2011d). On the performance of sorting by transpositions without using cycle graph. In Proceedings of the 6th Brazilian Symposium on Bioinformatics, pages 69–72, Brasília, Brazil.
Galvão, G. R. and Dias, Z. (2012a). GRAAu: Genome Rearrangement Algorithm Auditor. In Proceedings of the 4th International Conference on Bioinformatics and Computational Biology, pages 97–101, Las Vegas, NV, USA. Curran Associates, Inc.
Galvão, G. R. and Dias, Z. (2012b). On the approximation ratio for sorting by short swaps. In Proceedings of the 7th Brazilian Symposium on Bioinformatics, pages 120–125, Campo Grande, MS, Brazil.
Galvão, G. R. and Dias, Z. (2012c). On the approximation ratio of algorithms for sorting by transpositions without using cycle graphs. In Proceedings of the 7th Brazilian Symposium on Bioinformatics, volume 7049 of LNCS, pages 25–36, Campo Grande, MS, Brazil. Springer-Verlag.
Galvão, G. R. and Dias, Z. (2012d). On the performance of sorting permutations by prefix operations. In Proceedings of the 4th International Conference on Bioinformatics and Computational Biology, pages 102–107, Las Vegas, NV, USA. Curran Associates, Inc.
Grusea, S. and Labarre, A. (2011). The distribution of cycles in breakpoint graphs of signed permutations. CoRR, abs/1104.3353.
Kececioglu, J. D. and Sankoff, D. (1995). Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica, 13(1-2):80–110.
Labarre, A. (2012). Lower bounding edit distances between permutations. CoRR, abs/1201.0365.
Walter, M. E. M. T., Dias, Z., and Meidanis, J. (1998). Reversal and transposition distance of linear chromosomes. In Proceedings of the 5th International Symposium on String Processing and Information Retrieval, pages 96–102, Santa Cruz, Bolivia. IEEE Computer Society.
Walter, M. E. M. T., Dias, Z., and Meidanis, J. (2000). A new approach for approximating the transposition distance. In Proceedings of the 7th International Symposium on String Processing Information Retrieval, pages 199–208, Washington, DC, USA. IEEE Computer Society.
Publicado
23/07/2013
Como Citar
GALVÃO, Gustavo Rodrigues; DIAS, Zanoni.
Uma Ferramenta de Auditoria para Algoritmos de Rearranjo de Genomas. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 26. , 2013, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 17-22.
ISSN 2763-8820.
