Actas de congresos
On The Diameter Of Rearrangement Problems
Registro en:
9783319079523
Lecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). Springer Verlag, v. 8542 LNBI, n. , p. 158 - 170, 2014.
3029743
10.1007/978-3-319-07953-0_13
2-s2.0-84903941599
Autor
Lintzmayer C.N.
Dias Z.
Institución
Resumen
When we consider the Genome Rearrangements area, the problems of finding the distance of a permutation and finding the diameter of all permutations of the same size are the most common studied. In this paper, we considered problems for which no known results were presented regarding their diameters. We present some families of permutations whose distance is identical to the diameter for small sizes. They allowed us to gave bounds for the diameters of the problems we considered, as well as conjectures regarding the exact value. © 2014 Springer International Publishing. 8542 LNBI
158 170 Bafna, V., Pevzner, P.A., Genome Rearrangements and Sorting by Reversals (1993) Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), pp. 148-157 Bulteau, L., Fertin, G., Rusu, I., Pancake Flipping is Hard (2012) LNCS, 7464, pp. 247-258. , Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. Springer, Heidelberg Bulteau, L., Fertin, G., Rusu, I., Sorting by Transpositions is Difficult (2012) SIAM Journal on Computing, 26 (3), pp. 1148-1180 Caprara, A., Sorting Permutations by Reversals and Eulerian Cycle Decompositions (1999) SIAM Journal on Discrete Mathematics, 12 (1), pp. 91-110 Chitturi, B., Fahle, W., Meng, Z., Morales, L., Shields, C.O., Sudborough, I.H., Voit, W., An (18/11)n Upper Bound for Sorting by Prefix Reversals (2009) Theoretical Computer Science, 410 (36), pp. 3372-3390 Chitturi, B., Sudborough, I.H., Bounding Prefix Transposition Distance for Strings and Permutations (2012) Theoretical Computer Science, 421, pp. 15-24 Cibulka, J., On Average and Highest Number of Flips in Pancake Sorting (2011) Theoretical Computer Science, 412 (8-10), pp. 822-834 Dias, Z., Meidanis, J., Sorting by Prefix Transpositions (2002) LNCS, 2476, pp. 65-76. , Laender, A.H.F., Oliveira, A.L. (eds.) SPIRE 2002. Springer, Heidelberg Elias, I., Hartman, T., A 1.375-Approximation Algorithm for Sorting by Transpositions (2006) 375-Approximation Algorithm for Sorting by Transpositions, 3 (4), pp. 369-379 Eriksson, H., Eriksson, K., Karlander, J., Svensson, L., Wastlund, J., Sorting a Bridge Hand (2001) Discrete Mathematics, 241 (1-3), pp. 289-300 Fertin, G., Labarre, A., Rusu, I., Tannier, É., Vialette, S., Combinatorics of Genome Rearrangements (2009) Computational Molecular Biology, , MIT Press Galvão, G.R., Dias, Z., Computing Rearrangement Distance of Every Permutation in the Symmetric Group (2011) Proceedings of the 26th ACM Symposium on Applied Computing (SAC 22011), pp. 106-107. , Chu, W.C., Wong, W.E., Palakal, M.J., Hung, C.C. (eds.) ACM Gates, W.H., Papadimitriou, C.H., Bounds for Sorting by Prefix Reversal (1979) Discrete Mathematics, 27 (1), pp. 47-57 Hannenhalli, S., Pevzner, P.A., Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals (1999) Journal of the ACM, 46 (1), pp. 1-27 Heydari, M.H., Sudborough, I.H., On the Diameter of the Pancake Network (1997) Journal of Algorithms, 25 (1), pp. 67-94 Labarre, A., Edit Distances and Factorisations of Even Permutations (2008) LNCS, 5193, pp. 635-646. , Halperin, D., Mehlhorn, K. (eds.) ESA 2008. Springer, Heidelberg Lintzmayer, C.N., Dias, Z., On Sorting of Signed Permutations by Prefix and Suffix Reversals and Transpositions (2014) Proceedings of the 1st International Conference on Algorithms for Computational Biology (AlCoB 2014), Tarragona, Spain, pp. 1-12. , Dediu, A.H., Martín-Vide, C., Truthe, B. (eds.) Springer Lintzmayer, C.N., Dias, Z., Sorting Permutations by Prefix and Suffix Versions of Reversals and Transpositions (2014) LNCS, 8392, pp. 671-682. , Pardo, A., Viola, A. (eds.) LATIN 2014. Springer, Heidelberg Meidanis, J., Walter, M.M.T., Dias, Z., A Lower Bound on the Reversal and Transposition Diameter (2002) Journal of Computational Biology, 9 (5), pp. 743-745 Sharmin, M., Yeasmin, R., Hasan, M., Rahman, A., Rahman, M.S., Pancake Flipping with Two Spatulas (2010) Electronic Notes in Discrete Mathematics, 36, pp. 231-238. , International Symposium on Combinatorial Optimization (ISCO 2010) Walter, M.E.M.T., Dias, Z., Meidanis, J., Reversal and Transposition Distance of Linear Chromosomes (1998) Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE 1998), pp. 96-102. , IEEE Computer Society, Santa Cruz