An Audit Tool for Genome Rearrangement Algorithms
Abstract
This paper presents the results from the investigation of genome rearrangement algorithms, which find application in the estimation of evolutionary distance between species. The great majority of these algorithms are approximate, therefore we developed a tool for evaluating their results. We implemented and evaluated 16 approximate genome rearrangement algorithms using this tool. As a result, we showed that the approximation ratios of some of these algorithms are tight, contradicting some hypotheses raised in the literature, and we conjectured that the approximation ratios of some others also are.References
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.
Published
2013-07-23
How to Cite
GALVÃO, Gustavo Rodrigues; DIAS, Zanoni.
An Audit Tool for Genome Rearrangement Algorithms. In: THESIS AND DISSERTATION CONTEST (CTD), 26. , 2013, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 17-22.
ISSN 2763-8820.
